User Behavior Analysis in Practice 3: Order-based Filtering Using Binary Search

User Behavior Analysis in Practice 3: Order-based Filtering Using Binary Search

Target task:

We have a user events table T. Below is its structure and part of its data:

TimeUserIDEventTypeIDEventType
2022/6/1 10:2010727553Search
2022/6/1 12:1210780302Browse
2022/6/1 12:3610050935Submit
2022/6/1 13:2110486551Login
2022/6/1 14:4610378246Logout
2022/6/1 15:1910496264AddtoCart
2022/6/1 16:0010092965Submit
2022/6/1 16:3910707132Browse
2022/6/1 17:4010908843Search

Fields in table T:

Field nameData typeDescription
TimeDatetimeTime stamp of an event, accurate to milliseconds
UserIDIntegerUser ID
EventTypeIDIntegerEvent type ID
EventTypeStringEvent type name

Computing task:

Find the number of events under each type and that of distinct users who perform that type of event in the specified time period.

The first thing the task involves is to obtain data within a specified time period from huge amount of data.

Techniques involved:

Sort the original table by Time field and save the ordered data. This enables us to use binary search to perform the filtering without the need of traversing all data when trying to retrieve data in a specified time range, and thus can considerably speed up the filtering operation.

Sample code

1. Dump data from database and store it in a binary file ordered by time.

Stocked data: the data is retrieved from the database, sorted by time and written to a binary file:

A
1=connect("demo").cursor@x("select * from T order by Time")
2=file("T.btx").export@b(A1)

A1 Sort table T by time while retrieving data from it.

Newly-increased data: The newly-increased data is identified through time stamp. Each day after 0 o’clock we append the newly-generated data in the past day to a bin file:

A
1=connect("demo").cursor@x("select * from T where Time>=? && Time<? order by Time",date(now()-1), date(now()))
2=file("T.btx").export@ba(A1)

A1 Get data generated in the previous day through filtering condition to create a cursor. Data needs to be first sorted by time stamp.

A2 Fetch A1’s data from the cursor and append it to bin file T.btx. As the newly-increased data is identified according to time stamp, the new data is naturally generated later. There’s no need to sort-merge the new data and the old data. Just append the new data to the original file.

2. Perform fast filtering using binary search and then grouping & aggregation

Suppose we need to summarize data that falls in between 2022-03-15 and 2022-06-16:

A
1>start=date("2022-03-15","yyyy-MM-dd"),end=date("2022-06-16","yyyy-MM-dd")
2=file("T.btx").iselect@br(start:end,Time).groups(EventTypeID; EventType, count(1):Num, icount(UserID):iNum)

A2 iselect function reads records whose Time values are within the interval [start,end] from the file ordered by expression Time and return them as a cursor. In this case the time interval is closed. @r option indicates that not all Time values are distinct because there are concurrencies performed by multiple users; @b option enables reading data from a binary file.

The iselect function does not work with the option enabling parallel processing. In a single-task scenario, it is not necessarily that iselect is faster than the parallel-processing-based full traversal when the selected result set is large. In a multi-task scenario, parallel processing is futile (because the multiple CPUs will be fully occupied with handling concurrencies). In that case, the function has a great advantage.

Execution result:

EventTypeIDEventTypeNumiNum
1Login4033000393400
2Browse3578901348791
3Search2947931257539
4AddtoCart1845674175476
5Submit86734583375
6Logout4033000393400

Leave a Reply