1. Introduction
===============

Nowadays, various types of sensors, such as Kinect sensor \[[@B1-sensors-15-05344]\], inertial motion units \[[@B2-sensors-15-05344]\], ultrasound range sensor \[[@B2-sensors-15-05344]\], GPS \[[@B3-sensors-15-05344]\], Radio Frequency Identification (RFID), laser scanners \[[@B4-sensors-15-05344]\] and remote sensor networks \[[@B5-sensors-15-05344]\], have been used to perceive the physical environment, and many promising solutions \[[@B2-sensors-15-05344],[@B6-sensors-15-05344],[@B7-sensors-15-05344]\] have been proposed to realize the effective mapping from the physical world to the cyberspace. Among them, RFID technology is one of the most promising technologies. Based on geometric mapping, it has been increasingly used in various application scenarios, such as intelligent exhibition halls, goods tracking and congestion detection in logistics and distribution \[[@B8-sensors-15-05344]\], abnormal activity detection and insecurity factor detection in access control, and so on.

In the grocery industry, when various items, not only returnable transport carts, trolleys and kegs, but also valuable products, are equipped with RFID tags, item-level RFID infrastructures are established \[[@B9-sensors-15-05344]\]. They can be utilized to realize a wide range of smart applications, e.g., auto check-outs \[[@B9-sensors-15-05344]\], item-level valuable merchandise tracking \[[@B10-sensors-15-05344]\], vendor managed inventory \[[@B11-sensors-15-05344]\], smart price tags \[[@B9-sensors-15-05344]\], *etc.* \[[@B12-sensors-15-05344],[@B13-sensors-15-05344]\]. Among them, one of the more attractive applications is tracking customers' shopping paths. These paths can be captured based on identifying the moving trajectories of smart shopping carts/trolleys/keys which are tagged with RFID \[[@B14-sensors-15-05344]\]. Besides that, shopping carts/trolleys/keys featuring RFID readers can recognize valuable products put into the carts/trolleys/keys, if each valuable product is tagged with an RFID label. As a result, both the walking trajectories of customers and the corresponding purchase behaviors are automatically recorded in the RFID datasets, which are quite precious for mining in-depth knowledge about the shopping behaviors of customers.

Clearly, in the competitive retail climate, discovering insights from the shopping behaviors of customers and then turning these insights into promotion and customer care actions are crucial for enhancing retail business and service quality \[[@B15-sensors-15-05344]\]. Towards this vision, one fundamental work is to study customers' shopping paths in conjunction with their purchasing behaviors. The quick development of in-door positioning \[[@B6-sensors-15-05344],[@B7-sensors-15-05344],[@B16-sensors-15-05344],[@B17-sensors-15-05344],[@B18-sensors-15-05344],[@B19-sensors-15-05344],[@B20-sensors-15-05344],[@B21-sensors-15-05344],[@B22-sensors-15-05344],[@B23-sensors-15-05344]\] and data mining \[[@B24-sensors-15-05344],[@B25-sensors-15-05344],[@B26-sensors-15-05344],[@B27-sensors-15-05344],[@B28-sensors-15-05344],[@B29-sensors-15-05344],[@B30-sensors-15-05344],[@B31-sensors-15-05344],[@B32-sensors-15-05344]\] technologies sheds light on the above problem, and motivates us to consider building a bridge between RFID-based indoor mapping and advanced data mining techniques to explore customer's shopping behavior in depth.

Consequently, in this study, we propose a framework for mining actionable navigation patterns using multi-source RFID data, *i.e.*, shopping path data and RFID-supported customers' purchasing behavior data. Actionable navigation pattern \[[@B24-sensors-15-05344],[@B25-sensors-15-05344]\] is very useful for understanding behaviors of customers and can be applied to various applications, such as customer navigation, active advertising and recommendations, *etc.* In this framework, we first use the path graph to map the problem in the physical space to a problem in the cyber space, where shopping paths are represented by sequences of path segments. After the mapping between the physical space and the cyber space, the problem of RFID-based shopping path analytics is converted to sequential pattern analysis \[[@B26-sensors-15-05344]\], which has plenty of research in data mining field \[[@B27-sensors-15-05344],[@B28-sensors-15-05344],[@B29-sensors-15-05344],[@B30-sensors-15-05344],[@B31-sensors-15-05344],[@B32-sensors-15-05344]\] for further reference.

This paper is organized as follows: first, we introduce indoor mapping technologies and related terms in [Section 2](#sec2-sensors-15-05344){ref-type="sec"} and [Section 3](#sec3-sensors-15-05344){ref-type="sec"}, respectively. Then, in [Section 4](#sec4-sensors-15-05344){ref-type="sec"}, the framework for mining multi-source in-door RFID data is presented, and four modules are discussed in detail, which are: (1) mapping from the physical space to the cyber space; (2) data preprocessing; (3) pattern mining and (4) knowledge understanding and utilization. In [Section 5](#sec5-sensors-15-05344){ref-type="sec"}, we address a key problem existing in the data preprocessing module, which is how to identify the mainstream shopping transaction paths while wiping out unnecessary redundant and repeated details. An algorithm which can filter two types of redundant patterns is also proposed. Then, a simulated shopping path generator is discussed in [Section 6](#sec6-sensors-15-05344){ref-type="sec"}, and the experimental evaluation of the algorithm is given in [Section 7](#sec7-sensors-15-05344){ref-type="sec"}. Finally, we discuss the contributions towards a real supermarket scenario and conclude our work in [Section 8](#sec8-sensors-15-05344){ref-type="sec"} and [Section 9](#sec9-sensors-15-05344){ref-type="sec"}, respectively.

2. Indoor Mapping {#sec2-sensors-15-05344}
=================

To easily comprehend our proposed framework, we provide below a broad overview of indoor mapping technologies.

2.1. Overview
-------------

With the progress in sensor technology, many promising indoor-mapping solutions \[[@B1-sensors-15-05344],[@B2-sensors-15-05344],[@B3-sensors-15-05344],[@B6-sensors-15-05344],[@B7-sensors-15-05344],[@B16-sensors-15-05344],[@B17-sensors-15-05344]\], which can provide precise (or proximity), reliable and robust positioning services, have been proposed. Commonly, an indoor-mapping solution contains two components: (1) a physical-layer for sensing and (2) a software-realized data processing and location positioning, where the sensing capability is based on various available technologies, such as ultra-wideband (UWB), RFID, wireless local area network (WLAN), Bluetooth, ultrasound and video cameras, or the combination of these technologies \[[@B6-sensors-15-05344],[@B16-sensors-15-05344],[@B17-sensors-15-05344]\]. On the basis of sensing, location positioning can be achieved using positioning algorithms, which can be mainly divided into three categories: triangulation, scene analysis and proximity \[[@B17-sensors-15-05344]\]. Triangulation schemes employ geometrical property-based techniques, which are typically time of arrival (TOA), time difference of arrival (TDOA), round-trip time-of-flight (RTOF), angle of arrival (AOA) and received signal strength (RSS) \[[@B6-sensors-15-05344]\]. Scene analysis approaches commonly involve two phases: an offline phase of training and an online phase of positioning. In the offline phase, fingerprints of scenes are collected and stored; during the online recognition phase, machine learning methods (e.g., extreme learning machine \[[@B18-sensors-15-05344]\]) are adopted to compare the observed fingerprints with pre-measured fingerprints for position determination \[[@B17-sensors-15-05344]\].

2.2. RFID-Based Indoor Positioning
----------------------------------

Among the above technologies, RFID is an attractive option for coarse grained localization which provides proximity position information, because it is relatively cost-effective and is quite suitable for tracking a large number of items. Therefore, RFID technology is selected in our application of tracking shopping carts and purchased items in a supermarket.

Non-contact RFID positioning systems include three components: RFID readers, tags and servers, where tags can be active or passive. Active RFID tags equipped with internal batteries can broadcast their signals initiatively, and provide a much longer signal transmission range than passive tags; while passive tags are powered by signals transmitted from RFID readers \[[@B19-sensors-15-05344],[@B22-sensors-15-05344]\]. Several basic frequency bands are employed by RFID systems, which include low frequency (LF), high frequency (HF), very high frequency (VHF), ultra-high frequency (UHF) and microwave frequency. Different frequency bands offer different read ranges which normally vary from 10 cm to 12 m, and are suited for different applications \[[@B20-sensors-15-05344]\]. Representative RFID-based precise location sensing systems are SpotON \[[@B21-sensors-15-05344]\] and LANDMARC \[[@B22-sensors-15-05344]\], where reference tags are employed as landmarks. Typical work towards RFID- based proximity positioning includes tracking materials on construction job sites by combining proximity reads from a discrete range \[[@B23-sensors-15-05344]\].

Fault tolerance is another important issue for RFID-based positioning system. The faults (false positive/negative readings) may be caused by many factors, such as hardware failures (e.g., malfunction, running out of battery energy), multipath interference, or complex radio propagation \[[@B33-sensors-15-05344]\]. Countermeasures can be divided into two categories: physical solutions that are based on hardware performance improvement \[[@B34-sensors-15-05344]\], and intelligent software solutions that are based on spatial-temporal correlations/redundancy \[[@B33-sensors-15-05344],[@B35-sensors-15-05344]\].

3. Materials for the Study {#sec3-sensors-15-05344}
==========================

In this section, related concepts are defined, and the notations used in this study are summarized in [Table 1](#sensors-15-05344-t001){ref-type="table"}.

*Definition 1.* A *path segment s* is a directed edge associated with a direction symbol (*s.dir*), two terminal points (one is the start terminal point *s.b* and the other is the end terminal point *s.e*), and its length (*s.l*). The path segment only can be travelled from *s.b* to *s.e*. The reverse-order path segment of *s* is the path segment sharing the same edge with *s* but reverse direction, *i.e.*, *s~reverse~*, where *s~reverse~.dir* and *s.dir* are reverse, *s~reverse~.b* equals *s.e*, *s~reverse~.e* equals *s.b*, and *s~reverse~.l* and *s.l* are equal.

*Definition 2.* A *path graph G* is a directed graph, *i.e.*, *G* = (*V*, *E*), where *V* is the set of terminal points of path segments, and *E* is the set of path segments. Path graph *G* is an abstraction of the connections of path segments in a real field.

*Definition 3.* A *shopping path SP* is a sequence of path segments, *SP* = \<*s*~1~, *s*~2~,..., *s~n~*\>, where *s*~i+1~.*b* = *s~i~*.*e* and *s~j~* ∈ *E*, (1 ≤ *i* ≤ *n*−1, 1 ≤ *j* ≤ *n*). The beginning point and the ending point of *SP* can be represented as *SP*.*b* = *s*~1~.*b* and *SP*.*e* = *s~n~*.*e*.

*Definition 4*. There are several concepts related to shopping paths as given below:

\(1\) Given two shopping paths, *i.e.*, *SP* = \<*s*~1~, *s*~2~,..., *s~n~*\> and *SP\'* = $< s_{1}^{\prime},s_{2}^{\prime}\ldots s_{l}^{\prime} >$ (*l*≤*n*), if there exists *i*, such that $s_{1}^{\prime}$ = *S~i~*, $s_{2}^{\prime}$ = *s*~*i*+1~, ..., $s_{l}^{\prime}$ = *s*~*i*+*l*−1~, then *SP* is a super-sequence of *SP\'*, and *SP\'* is a subsequence of *SP* (denoted as *SP\'* ⊂ *SP*). We also call that *SP\'* is contained in *SP*.

\(2\) A navigation pattern *NP* means a subsequence of a shopping path.

\(3\) For a shopping path *SP* = \<*s*~1~, *s*~2~,...,*s*~*k*+1~,...,*s~n~*\>, the reverse-order path of *SP* is *SP~reverse~* =\<*s~n,reverse~*,...,*s*~*k*+1,reverse~, *s*~*k*,reverse~,*s*~2*reverse*~, *s*~1*reverse*~\>, where *s~i,reverse~* (1≤*i*≤*n*) is the reverse-order path segment of *s~i~*.

\(4\) Given a shopping path *SP* = \<*s*~1~, *s*~2~,...,*s~k~*, *s*~*k*+1~,...,*s~n~*\>, *SP~prefix~* = \<*s*~1~, *s*~2~,...,*s~k~*\>, is called a **prefix** of *SP*, and *SP~prefix~* = \<*s*~*k*+1~, *s*~2~,..., *s~n~*\> is called a suffix of *SP*, where 1≤*k*≤*n*.

\(5\) Given *n* shopping paths, *i.e.*, *SP*~1~, *SP*~2~, ..., *SP*~*n*-1~ and *SP~n~*, if *SP~i~*.*e* = *SP*~*i*+1~.*b* (1 ≤ *i* ≤ *n*−1) is satisfied, these shopping paths can be connected one after another, and the connection can be marked as *SP*~1~→*SP*~2~→...→*SP~n~*.

sensors-15-05344-t001_Table 1

###### 

Notations.

  Notation                          Description
  --------------------------------- -------------------------------------------------------------------------------
  *s, s~i~*                         A path segment
  *s~reverse~*                      The reverse-order path segment of *s*
  *s~i~.b, s~i~.e*                  The start terminal point, the end terminal point of *s~i~* respectively
  *t~i~*                            Unit time per unit length spent in *s~i~*
  *v~i~*                            A terminal point
  *T~i~*                            The itemset purchased in *s~i~*
  *G*                               A path graph
  *SP, SP\', SQ*                    A shopping path
  *SP\'* ⊂ *SP*                     SP is a super-sequence of *SP\'*, and *SP\'* is a subsequence of SP
  *STP, STP~prefix~, STP~suffix~*   A shopping transaction path
  Trans(*STP*)                      Transforming *STP* to a shopping path
  *i~item~*                         An item
  *i~item~* \< *STP*                *i~item~* is purchased in *STP*
  *D*                               A shopping transaction path database
  *S~item~*, \|*S~item~*\|          A set of items, and the number of its elements respectively
  *Γ~s~*                            The itemset sold in s
  *SIT*                             The Segment-Item Table
  *E~item~*                         The set of path segments that sell *i~item~*
  *IST, LT, PT*                     The Item-segment table, the Length table, and the Path-set table respectively

*Definition 5.* Given a shopping path *SP*, the connection between *SP* and its reverse-order path *SP~reverse~* (*i.e.*, *SP*→*SP~reverse~*) forms a symmetric pattern. If *SP*.*b* = *SP*.*e*, *SP* is called a loop pattern. Given a loop pattern *SP*, if *SP* repeats *n* (*n* ≥ 2) times successively, *i.e.*, *SP*→*SP*→...→*SP*, we call it a loop repeat pattern. Given a shopping paths, *i.e.*, *SP*, we call the pattern *SP*→*SP~reverse~*→*SP* a *palindrome-contained pattern*.

*Definition 6.* A *shopping transaction path* is a sequence of triples, *STP* = \<(*s*~1~,*t*~1~,*T*~1~), (*s*~2~,*t*~2~,*T*~2~), ..., (*s~n~*,*t~n~*,*T~n~*)\>, where (*s~i~*, *t~i~*, *T~i~*) means that a shopper purchases the itemset *T~i~* and spends *t~i~* unit time per unit length in the path segment *s~i~* (1≤*i*≤*n*).

*Definition 7.* Given a shopping transaction path, *i.e.*, *STP* = \<(*s*~1~,*t*~1~,*T*~1~), (*s*~2~,*t*~2~,*T*~2~), ..., (*s~n~*,*t~n~*,*T~n~*)\>, there are several concepts, which are relevant to shopping transaction paths, are given below:

\(1\) For simplicity, all *s~i~* (1≤*i*≤*n*) are called the path segments of shopping transaction path *STP*.

\(2\) For a given item *i~item~*, if *i~item~* ∈ *T*~1~∪*T*~2~∪...∪*T~n~*, we call *i~item~* is purchased in *STP*, *i.e.*, i~item~ \< STP.

\(3\) Given a fragment of *STP*, *i.e.*, *STP\'* = \<(*s~k~*,*t~k~*,*T~k~*), (*s~k~*~+1~,*t~k~*~+1~,*T~k~*~+1~), ..., (*s~l~*,*t~l~*,*T~l~*)\>(1≤*k*≤*l*≤*n*), we called *STP\'* a subsequence of *STP*, and *STP\'* is contained in *STP*.

\(4\) *STP~prefix~* = \<(*s*~1~,*t*~1~,*T*~1~), (*s*~2~,*t*~2~,*T*~2~), ..., (*s~k~*,*t~k~*,*T~k~*)\>, is called a prefix of *STP*, where 1\<*k*\<*n*. *STP~suffix~* = \<(*s~k~*~+1~,*t~k~*~+1~,*T~k~*~+1~), (*s~k~*~+2~,*t~k~*~+2~,*T~k~*~+2~), ..., (*s~n~*,*t~n~*,*T~n~*)\> is called a suffix of *STP*.

\(5\) Given a shopping transaction path, *STP* = \<(*s*~1~,*t*~1~,*T*~1~), (*s*~2~,*t*~2~,*T*~2~), ..., (*s~n~*,*t~n~*,*T~n~*)\>, if only path segments appear in *STP*, we transform it to a shopping path, *SP* = \<*s*~1~, *s*~2~,..., *s~n~*\>, which is called the shopping path of *STP* and denoted as *SP* = Trans(*STP*).

\(6\) Given *n* shopping transaction paths, *i.e.*, *STP*~1~, *STP*~2~, ..., *STP~n~*~-1~ and *STP~n~*, if Trans(*STP~i~*).*e* = Trans(*STP~i+~*~1~).*b* (1≤*i*≤*n*−1) is satisfied, these shopping transaction paths can be connected one after another, and the connection can be marked as *STP*~1~→*STP*~2~→...→*STP~n~*.

For example, *STP* = \<(*s*~1~,1, Ø),(*s*~2~,0.8,Ø),(*s*~3~,8,{*i*~1~,*i*~2~}),(*s*~4~,0.8,Ø),(*s*~5~,5,{*i*~3~})\> denotes that when the shopper visits *s*~1~, *s*~2~,..., *s*~5~ consecutively, he/she spends 1, 0.8, ..., 5 unit time per unit length in these path segments respectively. Meanwhile, the shopper purchases {*i*~1~,*i*~2~} in *s*~3~ and purchases {*i*~3~} in *s*~5~. *s*~1~, *s*~2~,..., *s*~5~ are all path segments of *STP*. Among them, *s*~1~ is the first path segment of *STP*, *s*~2~ is the second one, ..., and *s*~5~ is the last one. Because *i*~1~∈Ø∪Ø∪{*i*~1~,*i*~2~}∪Ø∪{*i*~3~}, we have *i*~1~ \< *STP*. *STP* can be transformed to a shopping path, that is to say Trans(*STP*) = \<*s*~1~, *s*~2~,..., *s*~5~\>.

*Definition 8.* A *mainstream of shopping path* is a shopping path without containing any loop repeat or palindrome-contained subsequence pattern. A shopping transaction path *STP* is a *mainstream of shopping transaction path*, if Trans(*STP*) is a mainstream of shopping path.

*Definition 9.* A *Segment-Item Table* (*SIT*), maintaining the information of items sold in each path segment, is denoted as below: where *s~i~* is a path segment, *Γ~s~i~~* is the itemset sold in *s~i~* (1≤*i*≤*W*), and *W* is the total number of path segments.

*Definition 10.* An *Item-Segment Table* (*IST*), maintaining the information about the segments where each item is sold, is denoted as below: where *i~item,j~* is an item, *E~item,j~* is the set of path segments that sell *i~item,j~* (1≤*j*≤*U*), and *U* is the total number of items.

*Definition 11.* A *Length Table* (*LT*), maintaining the length information of path segments, is denoted as below: where *s~i~* is a path segment, and *s~i.~.l* is the length of *s~i~* which can be obtained according to the length of normal trajectory of *s~i~* (1 ≤ *i* ≤ *W*).

4. System Framework of RFID Path Explorer {#sec4-sensors-15-05344}
=========================================

In this section, we describe the framework of the RFID supported paths and behaviors mining, called *RFID Path Explorer*.

The proposed framework consists of four modules: (1) mapping from the physical world to the cyber space; (2) data preprocessing; (3) a data mining mechanism; and (4) knowledge understanding and utilization (see [Figure 1](#sensors-15-05344-f001){ref-type="fig"}). [Table 2](#sensors-15-05344-t002){ref-type="table"} shows an example of shopping transaction path database which contains five shopping transaction paths. Below, we explain them in detail.

![The framework for RFID based shopping transaction path mining.](sensors-15-05344-g001){#sensors-15-05344-f001}

sensors-15-05344-t002_Table 2

###### 

An example of shopping transaction path database.

  *STP~id~*   Shopping Transaction Path
  ----------- ------------------------------------------------------------------------------------------------------------
  1           (AB, 0.8, Ø), (BC, 1, Ø), (CD, 4, {i~1~, i~2~}), (DE, 3, {i~3~}), (EF, 0.8, Ø), (FD, 0.8, Ø), (DK, 0.8, Ø)
  2           (AB, 0.9, Ø), (BC, 1, Ø), (CD, 5, {i~1~}), (DK, 0.8, Ø)
  3           (DK, 0.9, Ø), (KC, 0.8, Ø), (CD, 5, {i~2~}), (DE, 5, {i~3~})
  4           (BC, 0.8, Ø), (CD, 4, {i~1~}), (DK, 1, Ø), (KA, 0.8, Ø), (AD, 1, Ø), (DE, 4, {i~3~}), (EF, 1, Ø)
  5           (DK, 0.9, Ø), (KC, 1, Ø), (CD, 6, {i~2~, i~4~}), (DK, 1, Ø)

4.1. Indoor Mapping from the Physical World to the Cyberspace
-------------------------------------------------------------

The module of indoor mapping from the physical world (*PW*) to the cyber space consists of two steps as shown in [Figure 1](#sensors-15-05344-f001){ref-type="fig"}.

### 4.1.1. Step 1. RFID Deployment (Θ(·))

According to the task of application domain (*i.e.*, finding actionable navigation patterns for purchasing an item), suitable RFID devices should be chosen and deployed in a real field (*i.e.*, real supermarket). For instance, in our application, a RFID tag, which has a unique Electronic Product Code (*EPC*), is attached to each shopping trolley. RFID readers are located at various places of a supermarket, such as the entrance, the checkout, the gathering place for shopping carts, aisles and thoroughfares *etc.*, and used to identify shopping trolleys passing by. At the same time, when valuable items attached with RFID tags are put into a shopping trolley, they also can be recognized by this RFID-reader-equipped shopping trolley. Thus, both shoppers' path and behaviors can be captured (*C*(·)) and recorded. For the sake of robust, redundant multiple readers/tags \[[@B23-sensors-15-05344]\] and received signal strength functions of RFID devices \[[@B21-sensors-15-05344]\] can be added to promote the reliability of proximity location determination.

### 4.1.2. Step 2. Mapping (Φ(·))

Recorded raw RFID data can't be understood without the support of semantic information about these data. Therefore, attributes and features related to the analysis task should be abstracted from the physical world and mapped to the cyber-space. In the context of our application, a path graph *G* is used to abstract the connections of path segments, after RFID devices are deployed in a supermarket. An illustration of path graph is shown in [Figure 2](#sensors-15-05344-f002){ref-type="fig"}c, which is mapping from [Figure 2](#sensors-15-05344-f002){ref-type="fig"}b. A segment-item table (*SIT*) and an item-segment table (*IST*) are also extracted to reflect the items sold in each segment and the segments where each item is sold respectively. An example of *SIT* and *IST* is shown in [Table 3](#sensors-15-05344-t003){ref-type="table"}.

![An illustration of path graph (**a**) A photo of Real supermarket. (**b**) An illustration of a part of supermarket after RFID deployment. (**c**) An illustration of a part of path graph after mapping.](sensors-15-05344-g002){#sensors-15-05344-f002}

sensors-15-05344-t003_Table 3

###### 

An example of *SIT* and *IST*.

  Path Segment   Itemset                                      Itemset     Path Segment
  -------------- -------------------------------------------- ----------- --------------
  AB             NULL                                         *i*~1~      {CD, PZ}
  BC             NULL                                         *i*~2~      {CD, DE}
  CD             {*i*~1~, *i*~2~, *i*~6~*, i*~11~, *i*~12~}   *i*~3~      {GH, PQ, PZ}
  DE             {*i*~2~, *i*~15~}                            *i*~4~      {GJ}
  ...            ...                                          ...         ...
  PZ             {*i*~1~, *i*~3~, *i*~20~, *i*~5000~}         *i*~5000~   {PZ}

4.2. Preprocessing
------------------

After the raw RFID path and behavior data is captured, the preprocessing is shown in [Figure 3](#sensors-15-05344-f003){ref-type="fig"}.

### 4.2.1. Step 1. Data Ordering and Data Compression

Raw RFID path data has the form (*EPC*, *Loc*, *Time_stamp*), where *EPC* is the Electronic Product Code of the tag that uniquely represent a shopping cart, *Loc* is the identification location whose reader finds the tag, and *Time_stamp* is the time when the RFID reading takes place \[[@B36-sensors-15-05344]\]. These raw data firstly need to be sorted on *EPC* and *time*, and then be transformed to the form of stay record, *i.e.*, (*EPC*, *Loc*, *T_in*, *T_out*), where *T_in* is the time when the RFID tag enters the identification area, and *T_out* is the leave time \[[@B37-sensors-15-05344]\].

![RFID data preprocessing.](sensors-15-05344-g003){#sensors-15-05344-f003}

When an item (*i.e.*, *i~item~*) is put into a shopping cart (*i.e.*, *Cart*), a raw purchasing data (*i.e.*, (*Cart*, *i~item~*, *Time_stamp*)) is also generated, where *Time_stamp* is the time of detecting the item. And then, raw purchasing data is continuously produced, until the item is picked out of the shopping cart. Therefore, for an item, only the record of first reading needs to be saved, which marks purchasing of the item happens.

### 4.2.2. Step 2. Data Merging and Anomaly Detection

For a *EPC*, from the stay records, a whole trace record can be constructed, which has the form *EPC*: (*Loc*~1~, *T_in*~1~, *T_out*~1~), (*Loc*~2~, *T_in*~2~, *T_out*~2~), ..., (*Loc~w~*, *T_in~w~*, *T_out~w~*), where *Loc~i~* is the location where the tag is detected, *T_in~i~* and *T_out~i~* are the entering time and the leaving time of *Loc~i~* respectively, and (*Loc~i~*, *T_in~i~*, *T_out~i~*) is ordered by *T_in~i~* (1 ≤ *i* ≤ *W*) \[[@B38-sensors-15-05344]\]. For a whole trace record, if there are two same successive locations (*i.e.*, *Loc~i~* = *Loc~i+1~*), then (*Loc~i~*, *T_in~i~*, *T_out~i~*) and (*Loc~i+~*~1~, *T_in~i+~*~1~, *T_out~i+~*~1~) can be merged to (*Loc~i~*, *T_in~i~*, *T_out~i+~*~1~). Thus we have a whole trace record where any two successive locations are different.

Here, any two consecutive locations are required to meet spatial constraint \[[@B35-sensors-15-05344]\] that these two locations should be directly connected in the path graph. Two successive locations which cannot satisfy this constraint are labelled as an anomaly, and the anomaly should be checked further to infer/determine whether missed readings or false positive readings occur. If permanent/intermittent/transient faults leading to this anomaly can be identified, missed readings are filled in and false positive readings are discarded to make the whole trace record smoothly connected; otherwise, suspicious readings are removed and the remaining parts of the trace record are kept separately. This prior-knowledge based validation mechanism can further promote the reliability of sensing.

### 4.2.3. Step 3. Segment Extraction

In the supermark scenario, shopping carts are recycled and used by different shoppers at different shopping times. Thus, the whole trace record of a certain *EPC*, which is the proxy of a cart, commonly contains multiple shopping trips of various shoppers. Besides, path sequences of supermarket staff collecting shopping carts may also be contained. Therefore, in order to study customers' shopping behavior, it is necessary to extract individual shopping trips from the whole trace records.

For the above purpose, we develop a finite state machine model \[[@B39-sensors-15-05344]\] for shopping carts (see [Figure 4](#sensors-15-05344-f004){ref-type="fig"}) by referring to the real situation in supermarkets. In [Figure 4](#sensors-15-05344-f004){ref-type="fig"}, there are four states for a shopping cart: "idle", "shopping", "discarded" and "end" states. The "idle" state implies that the cart stays in the gathering place for shopping carts and is currently available. The "shopping" state indicates that the cart is in use by a shopper. The "discarded" state means that the cart is discarded midway by a shopper, and the "end" state implies the cart arriving at the checkout and the end of a shopping trip.

![The finite state machine model for shopping carts.](sensors-15-05344-g004){#sensors-15-05344-f004}

In the model, a state will be transformed to another one, if a certain event \[[@B40-sensors-15-05344]\] is triggered. The initial state of a cart may be "idle". If a "start" event happens, the "idle" state will become the "shopping" state, where the "start" event can be defined as the observation that a shopping cart leaving the gathering place and entering the main entrance. Then, the "shopping" state will be changed to the state of "discarded" if the "discarding" event happens or to the "end" state if the "end" event takes place. Both the "discarded" and the "end" states are followed by the "collection" event, and will be transformed to the "idle" state again. Here, the "discarding", the "end" and the "collection" events also should be defined according to the real situation. For example, we may define the "discarding" and the followed "collection" events as a long stay in a certain location and then moving to the gathering place directly, and the "end" event as a cart arriving checkout with items taken out of the shopping cart. Thus trace record segments can be extracted from a whole trace record, where each segment represents a single shopping trip.

### 4.2.4. Step 4. Assembling Segments into Shopping Transaction Paths

In order to analyze shopping paths, terminal-points focused trace record segments need to be further transformed to path-segments focused shopping transaction paths, which also combine the information of purchased items. The transform process is shown below.

First, given a trace record segment of a shopping cart (*Cart*), *i.e.*, *EPC_ID*: (*Loc*~1~, *T_in*~1~, *T_out*~1~), (*Loc*~2~, *T_in*~2~, *T_out*~2~), ..., (*Loc*~m~, *T_in*~m~, *T_out*~m~), and a length table (*LT*), the trace record segment can be converted to a shopping path with time information in the form of *EPC_ID*: (*s*~1~, *t*~1~), (*s*~2~, *t*~2~), ..., (*s~m~*~-1~, *t~m~*~-1~), where *s~i~* is the path segment connecting two successive locations (*i.e.*, *Loc~i~* and *Loc~i+1~*), and *t~i~* represents the time spent in *s~i~* per unit length of *s~i~* (1 ≤*i* ≤ *m*−1). That is to say, *t~i~* equals *time~i~* / *s~i~,.l*, where *time~i~* representing the time spent in *s~i~* is assumed as (*T_in~i~*~+1~+*T_out~i~*~+1~)/2-(*T_in~i~*+*T_out~i~*)/2 for simplicity (1 ≤ *i*≤ *m*−1), and *s~i~*.*l* is the length of *s~i~*. Second, suppose the corresponding set of purchasing records of *Cart* is {(*Cart*, *i~item,1~*, *Time_stamp~item,1~*), ..., (*Cart*, *i~item,n~*, *Time_stamp~item,n~*)}, where *T_in*~1~ ≤ *Time_stamp~item,j~* ≤ *T_out*~m~ (1≤*j*≤*n*). Then for each (*Cart*, *i~item,j~*, *Time_stamp~item,j~*), given *IST* = {(*i~item,1~*, *E~item,1~*),...,(*i~item,U~*, *E~item,U~*)}, there are four cases to decide which path segment *i~item,j~* is purchased in.

Case 1. If ∃ 2 ≤ *i* ≤ *m*-1, *T_out~i~* ≤ *Time_stamp~item,j~* ≤ *T_in~i+1~*, then obviously *i~item,j~* is purchased in *s~i~*.

Case 2. If *T_in~1~* ≤ *Time_stamp~item,j~* \< *T_out~1~*, then obviously *i~item,j~* is purchased in *s~1~*; if *T_in~m~*\<*Time_stamp~item,j~* ≤ *T_out~m~*, clearly, *i~item,j~* is purchased in *s~m-1~*.

Case 3. If ∃2 ≤ *i* ≤ *m*-1, *T_in~i~* \< *Time_stamp~item,j~* \< *T_out~i~*, *s~i~* ∈ *E~item,j~* and *s~i-~*~1~∉*E~item,j~*, then it can be deduced that *i~item,j~* is purchased in *s~i~*. If ∃2≤*i*≤*m*-1, *T_in~i~*\<*Time_stamp~item,j~* \< *T_out~i~*, *s~i~* ∉ *E~item,j~* and *s~i~*~-1~∈*E~item,j~*, then it can be derived that *i~item,j~* is purchased in *s~i~*~-1~.

Case 4. If ∃2 ≤ *i* ≤ *m*-1, *T_in~i~* \< *Time_stamp~item,j~* \< *T_out~i~*, *s~i~* ∈ *E~item,j~* and *s~i-~*~1*∈*~*E~item,j~*, we can't judge which path segment *i~item,j~* is purchased in among *s~i-~*~1~ and *s~i~*. In this case, besides the above conditions are met, if *T_in~i~* \< *Time_stamp~item,j~*≤(*T_in~i~+T_out~i~*)/2, *i~item,j~* is most probably purchased in *s~i-~*~1~; otherwise, if (*T_in~i~+T_out~i~*)/2 \< *Time_stamp~item,j~* \< *T_out*, *i~item,j~* is most likely purchased in *s~i~*.

Thus, after all items (*i.e.*, *i~item,j~* (1 ≤ *j* ≤ *n*)) are added to the corresponding item set of path segment where this item is purchased, we can obtain a shopping transaction path, *i.e.*, *EPC_ID*: \<(*s*~1~, *t*~1~, *T*~1~), (*s*~2~, *t*~2~, *T*~2~), ..., (*s*~m-1~, *t*~m-1~, *T*~m-1~)\>, where *T~i~* (1 ≤ *I* ≤ *m*-1) is the item set purchased in *s~i~*.

### 4.2.5. Step 5. Extracting Mainstreams of Shopping Transaction Paths

In the context of web browsing, Chen *et al.* \[[@B27-sensors-15-05344]\] first introduced the concept of maximal forward reference, and proposed a method of breaking a user session down into several maximal forward references if backward references appear in this session. However, several limitations still exist in the scheme of extracting maximal forward reference.

First, their extraction method assumes that backward references are all for easy of travelling, and not for browsing. But this assumption fails in the context of a real supermarket. There are two intentions for a shopper choosing to go backward. One is trying to explore and purchase in the backward reference, and the other is going through the backward reference to other interested sections, so the method of Chen *et al.* \[[@B27-sensors-15-05344]\] can't be applied here.

Second, their method throws away all backward references, which might provide important clues on shoppers' purchasing and navigation behaviors.

Third, after applying their method, the frequency of prefix sequence in front of symmetric pattern is increased unexpectedly. For instance, suppose there is a shopping path \< AB, BC, CD, DC, CE, EF, FG, GH, HG, GI \> shown in [Figure 5](#sensors-15-05344-f005){ref-type="fig"}, where two symmetric patterns exist, *i.e.*, \< CD, DC \> and \< GH, HG \>. After applying the method of Chen *et al.* \[[@B27-sensors-15-05344]\], the set of maximal forward shopping path is \< AB, BC, CD \>, \< AB, BC, CE, EF, FG, GH \>, \< AB, BC, CE, EF, FG, GI \>. We can find that the frequency of prefix sequence \< AB, BC \> unexpectedly becomes 3, while it is 1 in the original shopping path. The frequency of prefix sequence \< AB, BC, CE, EF, FG \> is converted to 2, while it is 1 in the original shopping path.

Fourth, a maximal forward reference terminates if a backward reference appears. Thus, a maximal forward reference will not contain any symmetric pattern. This may lead to an unexpected loss of important knowledge on symmetric pattern. For example, from the shopping path \< AB, BC, CD, DC, CE, EF, FG, GH, HG, GI \> shown in [Figure 5](#sensors-15-05344-f005){ref-type="fig"}, we know that this customer would like to go to the aisle of CD first, turn back to the main thoroughfare of EF, go forward to the aisle of GH, and then be back to the main thoroughfare again. The knowledge on customer's turning back disappears in the set of maximal forward shopping path.

Therefore, instead of finding maximal forward references, we present another new scheme called *extracting mainstream of shopping transaction path*, which reserves necessary symmetric patterns, but discards redundant and repeated details. This scheme is discussed in the next subsection in detail.

![An example for identifying maximal forward reference.](sensors-15-05344-g005){#sensors-15-05344-f005}

4.3. Mainstreams of Shopping Transaction Paths
----------------------------------------------

In the environment of a real supermarket, in order to choose items of interest, shoppers are inclined to push/pull shopping carts forward and backward. Symmetric patterns, loop patterns and redundant details may appear in shopping paths. In order to catch the mainstream of path sequences while discarding unnecessary redundant and repeated details, we put forward a scheme for identifying mainstream shopping transaction paths. In this scheme, we recognize that two types of redundant patterns need to be simplified, *i.e.*, loop repeat patterns and palindrome-contained patterns. .

### 4.3.1. Processing of Loop Repeat Patterns

Successive repeated path sequence loops actually reflect the same shopping interest and share the same behavior pattern, so these loops can be combined into one loop. For a shopping path, we can compress several repeat loops into one directly. For a shopping transaction path with a loop repeat pattern, *i.e.*, *STP~prefix~*→*STP*~1~→*STP*~2~→...→*STP~n~*→*STP~suffix~*, where *STP~i~* (*i* = 1,...,*n*) shares the same navigation pattern, these *STP~i~* (*i* = 1,...,*n*) also can be combined into a single *STP~combine~* = \<(*s*~1~, *t*~1~, *T*~1~), (*s*~2~, *t*~2~, *T*~2~),..., (*s~m~*, *t~m~*, *T~m~*)\>, so we also need to consider specifying values of *t~j~* and *T~j~* in *STP~combine~* (*j* = 1,...,*m*). The time spent in a path segment is normally comprised of two parts: walking time and time for exploring and purchasing. We consider that if a shopper tries to complete the task of exploring and purchasing in one loop (say *STP~combine~*), which is previously done in multiple loops (say *STP~i~* (*i* = 1,...,*n*)), time spent in the same path segment of loop should be cumulated, and itemsets purchased in the same path segment but in different loops also should be combined.

Therefore, we have the following definition for simplification of loop repeat pattern:

*Definition 12.* A shopping path containing loop repeat pattern, *i.e.*, *SP~prefix~*→*SP*$\overset{n}{\rightarrow}$*SP*→*SP~suffix~*, can be simplified as *SP~prefix~*→*SP*→ *SP~suffix~*. A shopping transaction path containing loop repeat pattern, *i.e.*, *STP~prefix~*→*STP*~1~→*STP*~2~→...→*STP~n~*→ *STP~suffix~*, where *STP~i~* = \<(*s*~1~, *t*~1,*i*~, *T*~1,*i*~), (*s*~2~, *t*~2,*i*~, *T*~2,*i*~),..., (*s~m~*, *t~m~*~,*i*~, *T~m~*~,*i*~)\>, all *STP~i~* share the same navigation pattern (say Trans(*TSP*) = \<*s*~1~, *s*~2~, ..., *s~m~*\>), and *m* is the number of path segments in *STP~i~* (*i* = 1,...,*n*), can be simplified as *STP~prefix~*→*STP~combine~*→ *STP~suffix~*, where *STP~combine~* = \<(*s*~1~, *t*~1~, *T*~1~), (*s*~2~, *t*~2~, *T*~2~),..., (*s~m~*, *t~m~*, *T~m~*)\>, *t*~walking~ is the smallest value of time spent per unit length in this shopping transaction path, *t~j~* and *T~j~* (*j* = 1,...,*m*) are defined as below: $$t_{j} = t_{walking} + \sum\limits_{i = 1}^{n}t_{purchasing}(j,i)~(j = 1,\ldots,m)$$ $$T_{j} = \underset{i = 1}{\overset{m}{\cup}}T_{j,i}~(j = 1,\ldots,m)$$

For instance, for the shopping path \<AB, BC, CD, DE, EB, BC, CD, DE, EB, BC, CF\> shown in [Figure 6](#sensors-15-05344-f006){ref-type="fig"}, loop \<BC, CD, DE, EB\> appears two times continuously and forms a loop repeat pattern, so this shopping path can be simplified as a mainstream of shopping path \<AB, BC, CD, DE, EB, BC, CF\>.

![An illustrative example of loop repeat pattern.](sensors-15-05344-g006){#sensors-15-05344-f006}

For a shopping transaction path \<(AB, 1, Ø), (BC, 2, Ø), (CD, 3, {*i*~1~}), (DE, 2, Ø), (EB, 6, {*i*~2~, *i*~3~}, (BC, 2, {*i*~4~}), (CD, 5, {*i*~6~, *i*~7~}), (DE, 1, Ø), (EB, 1, Ø), (BC, 1.1, Ø), (CF, 1, Ø)\>, a loop repeat pattern \<BC, CD, DE, EB\>→\<BC, CD, DE, EB\> appears. Triple elements having the same path segment but different loops should be combined, *i.e.*, (BC, 2, Ø) and (BC, 2, {*i*~4~}), (CD, 3, {*i*~1~}) and (CD, 5, {*i*~6~, *i*~7~}), *etc.* We take the combination of (BC, 2, Ø) and (BC, 2, {*i*~4~}) as an example. First, we obtain that *t*~walking~ equals 1, which is the smallest one in the set of time spent per unit length in this shopping transaction path. Then, time spent in BC per unit length (*t*~BC~) is computed as 1 + (2−1) + (2−1) = 3, and itemset in BC (*T*~BC~) is Ø∪{*i*~4~} = {*i*~4~}. Therefore, the result of the combination of (BC, 2, Ø) and (BC, 2, {*i*~4~}) is (BC, 3, {*i*~4~}). Thus this shopping transaction path can be simplified as a mainstream of shopping transaction path \< (AB, 1, Ø), (BC, 3, {*i*~4~}), (CD, 7, {*i*~1~, *i*~6~, *i*~7~}), (DE, 2, Ø), (EB, 6, {*i*~2~, *i*~3~}), (BC, 1.1, Ø), (CF, 1, Ø) \>. This mainstream shopping transaction path retains the main movement of a shopper and prunes unnecessary details.

### 4.3.2. Handling Palindrome-Contained Pattern

A palindrome-contained pattern, *i.e.*, *SP*→*SP~reverse~*→*SP*, is easily formed when a shopper compares the same kind of items in front of a shelf, and shows that shoppers hover in a *SP* navigation pattern. These three segments, *i.e.*, *SP*, *SP~reverse~* and the second *SP*, actually show the same shopping interest and share the same behavior pattern, so these successive segments can be simplified as *SP*. Thus, we have the following simplification method of palindrome-contained pattern 1:

*Definition 13*. A shopping path containing a palindrome-contained pattern, *i.e.*, *SP*→*SP~reverse~*→*SP*, can be simplified as *SP*. A shopping transaction path containing a palindrome-contained pattern, *i.e.*, *STP~prefix~*→*STP*~1~→*STP*~2~→*STP*~3~→*STP~suffix~*, where *STP~i~* = \<(*s*~1~, *t*~1,*i*~, *T*~1,*i*~), (*s*~2~, *t*~2,*i*~, *T*~2,*i*~),..., (*s~m~*, *t~m~*~,*i*~, *T~m~*~,*i*~)\> (*i* = 1, 3), *STP~2~* = \<(*s~m~*~,*reverse*~, *t~m~*~,2~, *T~m~*~,2~), (*s~m~*~-1,*reverse*~, *t~m~*~-1,2~, *T~m~*~-1,2~), ..., (*s*~1,*reverse*~, *t*~1,2~, *T*~1,2~)\>, can be simplified as *STP~prefix~*→*STP~combine~*→*STP~suffix~*, where *STP~combine~* = \<(*s*~1~, *t*~1~, *T*~1~), (*s*~2~, *t*~2~, *T*~2~),..., (*s~m~*, *t~m~*, *T~m~*)\>, *t*~walking~ is the smallest value of time spent per unit length in this shopping transaction path, *t~j~* and *T~j~* (*j* = 1,...,*m*) are defined as below: $$t_{j} = t_{walking} + \sum\limits_{i = 1}^{3}t_{purchasing}(j,i)~(j = 1,\ldots,m)$$ $$T_{j} = \underset{i = 1}{\overset{3}{\cup}}T_{j,i}~(j = 1,\ldots,m)$$

For example, for the shopping path \<AB, BC, CD, DE, ED, DC, CD, DE, EF\> shown in [Figure 7](#sensors-15-05344-f007){ref-type="fig"}, there is a palindrome-contained pattern \<CD, DE\>→\<ED, DC\>→\<CD, DE\>, so this shopping path can be simplified as a mainstream of shopping path \<AB, BC, CD, DE, EF\>.

![An illustrative example for palindrome-contained pattern.](sensors-15-05344-g007){#sensors-15-05344-f007}

In a shopping transaction path \<(AB, 1, Ø), (BC, 1, Ø), (CD, 3, Ø), (DE, 2, { *i*~1~}), (ED, 4, {*i*~2~, *i*~3~}), (DC, 6, { *i*~4~, *i*~5~, *i*~6~}), (CD, 5, {*i*~7~}), (DE, 1, Ø), (EF, 1, Ø)\>, a palindrome-contained pattern \<CD, DE\>→\<ED, DC\>→\<CD, DE\> appears. Triple elements sharing the same edge (without considering the direction of path segments) in this palindrome-contained pattern can be combined, *i.e.*, (CD, 3, Ø), (DC, 6, { *i*~4~, *i*~5~, *i*~6~}) and (CD, 5, {*i*~7~}) can be combined into a single triple, and (DE, 2, { *i*~1~}), (ED, 4, {*i*~2~, *i*~3~}) and (DE, 1, Ø) also can be merged into one. Take the combination process of (CD, 3, Ø), (DC, 6, {*i*~4~, *i*~5~, *i*~6~}) and (CD, 5, {*i*~7~}) as an example. First, we know that *t*~walking~ is 1, which equals the smallest of time spent per unit length in this shopping transaction path. *t*~CD~ is computed as 1 + (3 − 1) + (6 − 1) + (5 − 1) = 12, and *T*~CD~ is Ø∪{*i*~4~, *i*~5~, *i*~6~}∪{*i*~7~} = {*i*~4~, *i*~5~, *i*~6~, *i*~7~}, so the result of the merging is (CD, 12, {*i*~4~, *i*~5~, *i*~6~, *i*~7~}). Thus, this shopping transaction path can be simplified as \<(AB, 1, Ø), (BC, 1, Ø), (CD, 12, {*i*~4~, *i*~5~, *i*~6~, *i*~7~}), (DE, 5, {*i*~1~, *i*~2~, *i*~3~}), (EF, 1, Ø) \>.

5. Algorithm for Identifying Mainstreams of Shopping Transaction Paths {#sec5-sensors-15-05344}
======================================================================

The algorithm is an iterative process of filtering loop repeat patterns (*i.e.*, Function LRP_Filtering(STP)) and palindrome-contained patterns (*i.e.*, Function PCP_Filtering(STP)) for identifying mainstreams of shopping transaction path from shopping transaction paths, as shown in Algorithm 1.

Algorithm 1

Identifying mainstreams of shopping transaction paths

Input

: Shopping transaction paths

D

STP

Output

: Mainstreams of shopping transaction paths

D

MSTP

Method

:

1.  For each shopping transaction path *STP* in *D~STP~* do {

2.  while (loop repeat patterns and palindrome-contained patterns exist in *STP*) do {

3.  Call LRP_Filtering(*STP*) to filter loop repeat patterns

4.  Call PCP_Filtering(*STP*) to filter palindrome-contained patterns }

5.  Add *STP* to *D~MSTP~* }

6.  Return *D~MSTP~*.

5.1. Function LRP_Filtering(STP)
--------------------------------

Given a shopping transaction path *STP* = \<(*s*~0~, *t*~0~, *T*~0~), (*s*~1~, *t*~1~, *T*~1~),..., (*s~n~*, *t~n~*, *T~n~*)\>, the process of filtering loop repeat patterns is an iterative procedure to find the start position of the loop (say *µ*) and the number of path segments in the loop (say λ), such that *s~µ~*~+*i*~ = *s*~µ+λ+i~ (*i* = 0,1,..., λ − 1; µ+λ+*i* ≤ *n*). If *µ* and *λ* satisfying the above conditions are found, the fragments \<(*s*~µ~, *t*~µ~, *T*~µ~),..., (*s*~µ+λ-1~, *t*~µ+λ-1~, *T*~µ+λ-1~)\> and \<(*s*~µ+λ~, *t*~µ+λ~, *T*~µ+λ~),..., (*s*~µ+2λ-1~, *t*~µ+2λ-1~, *T*~µ+2λ-1~)\> in *STP* form a loop repeat pattern. This procedure is given in sub-function Find_RepeatLoops(*STP*), and three data structures (*i.e.*, path vector, hash table, and list of loop candidates) are used:

Definition 14. A *path vector* (say *PV*) is a vector of pair (*s*, *pos*), where *s* is a path segment and *pos* is the previous position of *s* in *PV*. A *hash table* (say *HT*) stores the current position (*i.e.*, *cur_pos_seg*) for each path segment (*i.e.*, *s*), and a hash function *f* is defined in *HT*, such that *HT*\[*f*(*s*)\] = *cur_pos_seg*. A *list of loop candidates* (say *List*) is a list of triple (*b_pos*, *e_pos*, *cur_pos*) representing a loop candidate (*i.e.*, the fragment \<*PV*\[*b_pos*\].*s*, *PV*\[*b_pos*+1\].*s*, ..., *PV*\[*e_pos*\].*s*\>), where *cur_pos* is the current matching position between *b_pos* and *e_pos*. Based on these definitions, we have the following Function LRP_Filtering(*STP*), where the key part is the sub-function Find_RepeatLoops(*SP*).

Function.

LRP_Filtering(

STP

)

Method:

1.  While repeat loop pattern is found, do{

2.  (µ, λ, *n_loops*)←Find_RepeatLoops(trans(*STP*))

3.  If repeat loop pattern is found, do {

4.  For *STP*, combine *n_loops* fragments, *i.e.*, \<(*s*~µ~, *t*~µ~, *T*~µ~),..., (*s*~µ+λ-1~, *t*~µ+λ-1~, *T*~µ+λ-1~)\>, \<(*s*~µ+λ~, *t*~µ+λ~, *T*~µ+λ~),..., (*s*~µ+2λ-1~, *t*~µ+2λ-1~, *T*~µ+2λ-1~)\>, ..., \<(*s*~µ +\ (*n_loops*-1)\ ×\ *λ*~, *t~µ~*~+(*n_loops*-1)×λ~, *T~µ~*~+(*n_loops*-1)×λ~),..., (*s~µ~*~+*n_loops*×λ-1~, *t~µ~*~+*n_loops*×*λ*-1~, *T~µ~*~+*n_loops*×*λ*-1~)\>, to form a new *STP* according to Definition 12.} }

5.  Return *STP*

Sub-Function.

Find_RepeatLoops(

SP

)

1.  Initialize *PV*, *HT* and *List* as empty

2.  Suppose *SP* = \<*s*~0~, *s*~1~, ..., *s~n~*\>. For each path segment *s~i~* in *SP*, do {

3.  If *s~i~* is a key in *HT*, let *cur_pos_seg=HT*\[*f*(*s~i~*)\]; otherwise, insert a key-value pair (*s~i~*, "null") to *HT* and let *cur_pos_seg*="null". Push the pair (*s~i~*, *cur_pos_seg*) onto *PV*, and get the position of this pair in *PV* (say *new_cur_pos_seg*). Set *HT*\[*f*(*s~i~*)\] to be *new_cur_pos_seg* in *HT*.

4.  For each triple (*b_pos*, *e_pos*, *cur_pos*) in *List*, do {

5.  If *PV*\[*cur_pos*+1\].*s* equals to *s~i~*, do {

6.  If (*cur_pos*+1) equals to *e_pos*, repeat loops are found. Let *µ* be *b_pos*, *λ* be *e_pos*-*b_pos*+1. Call *n_loops*←Test_RepeatLoops(*SP*, *µ*, *λ*, 2). Return the triple (µ,λ, *n_loops*) and exit this sub-function. Otherwise, let *cur_pos*++ and update this triple in *List*. }

7.  Else delete this triple from *List*. }

8.  If *cur_pos_seg* equals to *new_cur_pos_seg*-1, repeat loops are found. Let µ be *cur_pos_seg* and λ be 1. Call *n_loops*←Test_RepeatLoops(*SP*, µ, λ, 2). Return the triple (µ,λ, *n_loops*) and exit this sub-function.

9.  While *cur_pos_seg* isn't "null", do {

10. Generate a candidate triple (*cur_pos_seg*, *new_cur_pos_seg*-1, *cur_pos_seg*) and add it to *List*. Let *cur_pos_seg* = *PV*\[*cur_pos_seg*\].*pos*.}}

11. No repeat loop pattern is found. Return the triple ("null", "null", "null").

Sub-Function.

Test_RepeatLoops(

SP

, µ, λ,

n_loops

)

1.  If μ + (*n_loops* + 1) × λ − 1 ≤ *n* and \<*s~μ~*, *s~μ~*~+1~, ..., *s~μ~*~+λ-1~\> = \<*s~μ~*~+*n_loops*×*λ*~, *s~μ~*~+~*~n_loops~*~×*λ*+1~, ..., *s~μ~*~+(*n_loops*+1)×*λ*-1~\>, *n_loops*++ and then call *n_loops*←Test_RepeatLoops(*SP*, µ, λ, *n_loops*).

2.  Return *n_loops*.

We use a running example to explain the running process of sub-function Find_RepeatLoops(SP). Given a shopping path *SP* = \<EA, AB, BC, CD, DE, EA, AB, BE, EA, AB, BE, EG, GD, DK\>, the function reads path segments in SP one by one, and the process of finding loop repeat pattern is shown below.

For the first path segment EA, EA cannot be found as a key in empty *HT*, so the key-value pair (EA, "null") is inserted to *HT*, and the pair (EA, "null") is pushed onto an empty *PV*. The position of this pair in *PV* is 0. Therefore, the value associated with EA is changed to 0 in *HT*. *cur_pos_seg* (which is "null") doesn't equal to *new_cur_pos_seg*-1 (which is -1). *List* still remains empty.

For the second path segment AB, similar operations are done. After operations, the key-value pair (AB, 1) is added in *HT*, and the pair (AB, "null") is pushed onto *PV*.

Similarly, after reading the third path segment BC, the fourth CD, and the fifth DE, pairs (BC, 2), (CD, 3), (DE, 4) are inserted into *HT*, and pairs (BC, "null"), (CD, "null"), (DE, "null") are pushed onto *PV* sequentially. Because *cur_pos_seg* keeps "null", no candidate is generated.

For the sixth path segment EA, it is found as a key in *HT* and *cur_pos_seg* is 0, which is the position of previous EA in *PV*. Push the pair (EA, 0) onto *PV* and set the value associated with EA (*i.e.*, *HT*\[*f*(EA)\]) to be 5 in *HT*. Because *cur_pos_seg* is not "null", a candidate (0, 4, 0) is generated and added to *List*. And then, *cur_pos_seg* = *PV*\[0\].*pos =* "null", so no candidate is generated here.

For the seventh path segment AB, the pair (AB, 1) is pushed onto *PV* and *HT*\[*f*(AB)\] is set as 6. Since there is a loop candidate (*i.e.*, triple (0, 4, 0)) in *List*, we need to compare AB with the next path segment of this candidate (*i.e.*, *PV*\[0+1\].*s*). Both of them are AB and they are matching, so we set this triple to be (0, 4, 1). Because *cur_pos_seg* is 1, a new candidate (1, 5, 1) is produced and there are two candidates in *List* now.

When reading the eighth one BE, the pair (BE, 7) is pushed onto *PV* and *HT*\[*f*(BE)\] is 7. For the candidate (0, 4, 1), the next path segment is *PV*\[1+1\].*s*=BC, which does not match BE. So this candidate should be deleted from *List*. For the candidate (1, 5, 1), the next path segment, *i.e.*, *PV*\[1+1\].*s*=BC, does not match BE, so this candidate also needs to be pruned. No new candidate is generated, since *cur_pos_seg* equals to "null".

For the ninth one EA, the pair (EA, 5) is added at the end of *PV* and the value associated with EA is set as 8 in *HT*. Similarly, two new candidates (5, 7, 5) and (0, 7, 0) are obtained and added to *List*.

Similarly, when reading the tenth path segment AB, the pair (AB, 6) is pushed onto *PV* and *HT*\[*f*(AB)\] is set as 9. For candidates, triple (5, 7, 5) becomes (5, 7, 6), and triple (0, 7, 0) is converted to (0, 7, 1). And two new candidates, *i.e.*, triple (6, 8, 6) and triple (1, 8, 1), are generated.

When reading the eleventh one BE, the pair (BE, 7) is added at the end of *PV* and *HT*\[*f*(BE)\] is set as 10. For the candidate (5, 7, 6), the next path segment *PV*\[6+1\].*s* equals to BE, and is the last one in this candidate. Thus repeat loops are found, and µ, λ are 5, 3 respectively. And then, we call Test_RepeatLoops(*SP*, 5, 3, 2). Since \<*s*~5~, *s*~6~, *s*~7~\> (*i.e.*, \<EA, AB, BE\>) are not equal to \<*s*~11~, *s*~12~, *s*~13~\> (*i.e.*, \<EG, GD, DK\>), *n_loops* which equals 2 is returned. Thus, we have *n_loops* equals 2.

5.2. Function PCP_Filtering (STP)
---------------------------------

Given a shopping transaction path *STP* = \<(*s*~0~, *t*~0~, *T*~0~), (*s*~1~, *t*~1~, *T*~1~),..., (*s~n~*, *t~n~*, *T~n~*)\>, the procedure of filtering palindrome-contained patterns (*i.e.*, *STP*~1~→*STP*~2~→*STP*~3~, where Trans(*STP*~1~), the reverse-order path of Trans(*STP*~2~), and Trans(*STP*~3~) are equal (say *SP*)) is an iterative process of finding the start position of palindrome-contained pattern (say µ), and the number of path segments of *SP* (say *λ*), such that *s~µ~*~+*i*~ = *s~µ~*~+2*λ*-*i*-1,*reverse*~ = *s~µ~*~+2*λ*+*i*~ (*i* = 0,1,..., *λ* − 1; µ + 2*λ* + *i* ≤ *n*), where *s~µ~*~+2*λ*-*i*-1,*reverse*~ is the reverse-order path segment of *s~µ~*~+2*λ*-*i*-1~. If *µ* and *λ* satisfying the above conditions are found, the connections of three fragments \<(*s~µ~*, *t~µ~*, *T~µ~*),..., (*s*~µ+λ-1~, *t*~µ+λ-1~, *T*~µ+λ-1~)\>, \<(*s*~µ+λ~, *t*~µ+λ~, *T*~µ+λ~),..., (*s~µ~*~+2*λ*-1~, *t*~µ+2λ-1~, *T*~µ+2λ-1~)\> and \<(*s*~µ+2λ~, *t*~µ+2λ~, *T*~µ+2λ~),..., (*s*~µ+3λ-1~, *t*~µ+3λ-1~, *T*~µ+3***λ***-1~)\> in *STP* form a palindrome-contained pattern. This procedure is presented in the sub-function Find_PCP(*STP*), and three data structures (*i.e.*, vector of path segment, list of candidate, and list of candidate suffix) are adopted.

*Definition 15.* A *vector of path segment* (say *V*) stores path segments. Suppose a potential palindrome-contained pattern is *SP*→*SP~reverse~*→*SP*. A *list of candidate* (say *LC*) is a list of triple (*b_pos*, *e_pos*, *cur_pos*), and each triple represents a candidate *SP* (*i.e.*, the fragment \<*V*\[*b_pos*\], *V*\[*b_pos*+1\], ..., *V*\[*e_pos*\]\>), where *cur_pos* is the current matching position between *b_pos* and *e_pos*. A *list of candidate suffix* (say *LCS*) is a list of pair (*inter_posi*, *e_posi*), and each pair represents a candidate suffix of *SP* (*i.e.*, the fragment \<*V*\[*inter_posi*\], *V*\[*inter_posi*+1\], ..., *V*\[*e_posi*\]\> ).

Based on the above definition, we have the following Function PCP_Filtering (*STP*):

Function.

PCP_Filtering(

STP

)

Method:

1.  While palindrome-contained pattern is found, do{

2.  (µ, λ)←Find_PCP(trans(*STP*))

3.  If palindrome-contained pattern is found, do {

4.  For *STP*, combine fragments \<(*s*~µ~, *t*~µ~, *T*~µ~),..., (*s*~µ+λ-1~, *t*~µ+λ-1~, *T*~µ+λ-1~)\>, \<(*s*~µ+λ~, *t*~µ+λ~, *T*~µ+λ~),..., (*s*~µ+2λ-1~, *t*~µ+2λ-1~, *T*~µ+2λ-1~)\> and \<(*s*~µ+2λ~, *t*~µ+2λ~, *T*~µ+2λ~),..., (*s*~µ+3λ-1~, *t*~µ+3λ-1~, *T*~µ+3λ-1~)\> to form a new *STP* according to Definition 13.} }

5.  Return *STP*

Sub-Function.

Find_PCP(

SP

)

1.  Initialize *V*, *LC* and *LCS* as empty

2.  Suppose *SP* = \<*s*~0~, *s*~1~, ..., *s~n~*\>. For each path segment *s~i~* in *SP*, do {

3.  If *V* is not empty, do {

4.  Get the position of the last element of *V* (say *cur_pos_seg*), and compare the last element of *V* with *s~i~*. If they are reverse-order, let variable *reverse-order* be true. Otherwise, let variable *reverse-order* be false. }

5.  Else let *reverse-order* be false.

6.  Push *s~i~* onto *V*.

7.  For each candidate triple (*b_pos*, *e_pos*, *cur_pos*) in *LC*, do {

8.  If *cur_pos* is "null", let *cur_pos* be *b_pos*; otherwise, let *cur_pos* be added by 1.

9.  Compare *V*\[*cur_pos*\] with *s~i~*. If they are same, do {

10. Let this triple be (*b_pos*, *e_pos*, *cur_pos*) and update it in *LC*. If *cur_pos* equals to *e_pos*, then a palindrome-contained pattern is found. Let µbe *b_pos*, λbe *e_pos*-*b_pos*+1, return the pair of µand λ, and exit this sub-function. }

11. Else delete this candidate triple from *LC*. }

12. For each pair (*inter_posi*, *e_posi*) in *LCS*, do {

13. If *inter_posi*-1 0, and *V*\[*inter_posi*-1\] and *s~i~* are reverse-order, set this pair as (*inter_posi*-1, *e_posi*) in *LCS*, and generate a new candidate (*inter_posi*-1, *e_posi*, "null") in *LC*. Otherwise, delete this pair from *LCS*. }

14. If *reverse-order* is true, do {

15. Produce a candidate (*cur_pos_seg*, *cur_pos_seg*, "null") and insert it to *LC*.

16. Generate a candidate suffix (*cur_pos_seg*, *cur_pos_seg*) and add it to *LCS*. } }

17. No palindrome-contained pattern is found. Return the pair of "null" and "null".

In the following, we illustrate a running example to show the running procedure of sub-function Find_PCP(SP). For instance, given a shopping path SP = \<AB, BC, CD, DE, EF, FE, ED, DC, CD, DE, EF, FG\>, its process of finding palindrome-contained pattern is as described below:

For the first path segment AB, simply let *reverse-order* be false and push AB onto *V*. When reading the second path segment BC, we compare the last element of *V*, which is AB, with BC. Because they are not reverse-order, *reverse-order* is false. Then, we push BC onto *V*.

Similarly, we push CD, DE, EF onto *V*. And no candidate or candidate suffix is generated.

For the sixth path segment FE, since the last element of *V* (EF) and FE are reverse-order, *reverse-order* is true. We push FE onto *V*. A candidate (4, 4, "null") and a candidate suffix (4, 4) are generated.

When reading the seventh path segment ED, *reverse-order* is false, and ED is pushed onto *V*. For candidate (4, 4, "null"), we compare *V*\[4\] (EF) with ED and they do not match, so we delete this candidate from *LC*. For candidate suffix (4, 4), since *V*\[3\] (DE) is reverse-order path segment of ED, this candidate suffix becomes (3, 4) and a new candidate (3, 4, "null") is generated.

When reading the eighth path segment DC, *reverse-order* is also false, and DC is pushed onto *V*. For candidate (3, 4, "null"), since *V*\[3\] (DE) and DC do not match we also prune this candidate from *LC*. For candidate suffix (3, 4), *V*\[2\] (CD) and DC are reverse-order, so this candidate suffix turns to (2, 4) and a new candidate (2, 4, "null") is produced.

When reading the ninth path segment CD, *reverse-order* is true and CD is pushed onto *V*. For candidate (2, 4, "null"), since *V*\[2\] (CD) and CD match, this candidate turns to (2, 4, 2). For candidate suffix (2, 4), since *V*\[1\] (BC) and CD are not reverse-order, we delete this candidate suffix from *LCS*. Because *reverse-order* is true, a candidate (7, 7, "null") and a candidate suffix (7, 7) are produced.

When reading the tenth one DE, *reverse-order* is false and DE is pushed onto *V*. For candidate (2, 4, 2), since *V*\[3\] (DE) and DE are matching, it turns to (2, 4, 3). For candidate (7, 7, "null"), it is deleted for mismatch. For candidate suffix (7, 7), since *V*\[6\] (ED) and DE are reverse-order, this candidate suffix becomes (6, 7) and a new candidate (6, 7, "null") is added to *LC*.

Then for the eleventh one EF, *reverse-order* is also false and EF is pushed onto *V*. For candidate (2, 4, 3), since *V*\[4\] (EF) and EF are matching, this candidate becomes (2, 4, 4). Thus, a palindrome-contained pattern is found, and µ, *λ* are 2, 3 respectively.

6. Generation of Synthetic Shopping Transaction Paths {#sec6-sensors-15-05344}
=====================================================

In order to generate a synthetic workload, we build an agent \[[@B41-sensors-15-05344]\]-based simulator to simulate the scenario of an individual shopping trip. The complete flow diagram for this simulator is shown in [Figure 8](#sensors-15-05344-f008){ref-type="fig"}, which mainly includes four steps: construction of a path graph, initialization of customer agents, generating a shopping transaction path, and attaching extra loop repeat patterns and palindrome-contained patterns. Among them, Step 4 is optional for testing. Steps 2, 3 and 4 can be performed repeatedly for \|*D*\| times and then a database of shopping transaction paths *D* will be produced. In the following, we discuss these four steps in detail. For the sake of easy reference, the meanings of various variables used in our simulator are summarized in [Table 4](#sensors-15-05344-t004){ref-type="table"}.

![Flow diagram for generating a shopping transaction path.](sensors-15-05344-g008){#sensors-15-05344-f008}

sensors-15-05344-t004_Table 4

###### 

Meaning of various variables in our simulations.

  Notation                                                               Description
  ---------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------
  *n~terminal_points~, n~path_segments~*                                 The number of terminal points, path segments in path graph *G* respectively
  *n~items~*                                                             The number of different items
  *ShoppingTime(i~item~)*                                                The shopping time for *i~item~*
  *j*                                                                    A shopper
  *speed~normal,\ j~, speed ~j~*                                         The normal, actual moving speed for *j* respectively
  *n~plan,\ j~*                                                          The number of different planned-purchasing items for *j*
  *n~interest,\ j~*                                                      The number of different items that *j* feels interested in
  *L~plan,\ j~*                                                          A set of planned-purchasing items for *j*
  *L~interest,\ j~*                                                      A set of items that *j* feels interested in
  *S~plan,\ j~*                                                          A set of path segments that *j* plans to visit
  *S~interest,\ j~*                                                      A set of path segments that *j* feels interested in
  *μ~speed_normal~*, *σ~speed_normal~*                                   The mean, the standard deviation of the Gaussian distribution of *speed~normal,j~*
  *lower_bound~nplan,j~, upper_bound~nplan,j~*                           The lower bound, the upper bound of the uniform distribution of *n~plan,\ j~* on integers respectively
  *n~extra_interest,\ j~*                                                The number of additional items (besides items in L~plan,\ j~) that *j* feels interests in
  *lower_bound~nextra_interest,\ j~, upper_bound~nextra_interest,\ j~*   The lower bound, the upper bound of the uniform distribution of *n~extra_interest,j~* on integers respectively
  *μ~ShoppingTime~*(*i~item,k~*), *σ~ShoppingTime~*(*i~item,k~*)         The mean, the standard deviation of the Gaussian distribution of *ShoppingTime*(*i~item,k~*) respectively
  *PerceivedTimePressure~j~*                                             The perceived time pressure for j
  *σ~PerceivedTimePressure~*                                             The standard deviation of the Gaussian distribution of *PerceivedTimePressure~j~*
  *time~s,\ j~*                                                          Time spent in path segment *s* for *j*
  *time~walking,\ s,\ j~, time~shopping,\ s,\ j~*                        Time spent for walking, shopping in path segment *s* for *j* respectively
  *Distance(j, s)*                                                       The distance between *j* and path segment s
  \|*D*\|                                                                The number of shopping transaction paths in *D*
  *L*                                                                    The average number of path segments in shopping transaction paths
  *n~LRP~, n~PCP~*                                                       The number of loop repeat patterns, palindrome-contained patterns respectively

6.1. Step 1. Construction of Path Graph G
-----------------------------------------

A path graph, the container for customer agents moving in, is constructed in this step. We need to specify the components of a path graph: the set of terminal points of path segments, and the set of path segments. A length table *LT* and a segment-item table *SIT* are also needed to be produced. And then, an item-segment table *IST* can be derived.

6.2. Step 2. Initialization of a Shopper Agent
----------------------------------------------

This step includes the following two sub-steps.

### 6.2.1. Shopper Agent Initialization

In this sub-step, a shopper agent representing an in-store shopper (say *j*) is initialized. Each shopper agent has the following parameters, which need to be specified:

1.  Normal moving speed *speed~normal,\ j~*

*speed~normal,\ j~* means the normal moving speed of *j*, which is derived from a Gaussian distribution with mean *μ~speed_normal~* and standard deviation *σ~speed_normal~*.

2.  Number of different planned-purchasing items *n~plan~*~,\ *j*~

*n~plan~*~,\ *j*~ represents the number of different items that are planned to be purchased by *j*, and is derived from an uniform distribution on the integers *lower_bound~nplan,\ j~*, *lower_bound~nplan,\ j~* + 1, ..., *upper_bound~nplan,\ j~*.

3.  A set of planned-purchasing items *L~plan~*~,\ *j*~

*L~plan~*~,\ *j*~ means the set of different items that are planned to be purchased, and can be written as {*i~item~*~,1~, *i~item~*~,2,~ ..., *i~item,nplan,\ j~*}.

4.  Number of different items that *j* feels interested in (say *n~interest~*~,\ *j*~)

*n~interest~*~,\ *j*~ is the sum of *n~plan~*~,*j*~ and the number of additional items (besides items in *L~plan~*~,\ *j*~) that *j* feels interests in (say *n~extra_interest~*~,\ *j*~). The latter is derived from an uniform distribution on the integers *lower_bound~nextra_interest,\ j~*, *lower_bound~nextra_interest,\ j~* + 1, ..., *upper_bound~nextra_interest,\ j~*.

5.  A set of items that *j* feels interested in (say *L~interest~*~,\ *j*~)

*L~interest~*~,\ *j*~ has the form {*i~item~*~,1~, *i~item~*~,2~, ..., *i~item,ninterest,\ j~*}, and each item *i~item~*~,*k*~ is associated with its shopping time *ShoppingTime*(*i~item~*~,*k*~) (*k* = 1, 2,..., *n~interest~*~,\ *j*~). *ShoppingTime*(*i~item~*~,*k*~) is derived from a Gaussian distribution with mean *μ~ShoppingTi\ me~*(*i~item,k~*) and standard deviation *σ~ShoppingTi\ me~*(*i~item,k~*).

6.  Perceived time pressure \[[@B42-sensors-15-05344]\] *PerceivedTimePressure~j~*

*PerceivedTimePressure~j~* represents *j*'s perceived time pressure during a shopping trip, and significantly affects *j*'s moving speed. *PerceivedTimePressure~j~* is also derived from a Gaussian distribution with mean 1 and standard deviation *σ~PerceivedTimePressure~*.

For *j*, his/her actual moving speed *speed~j~* can be simply computed as below:

### 6.2.2. Generating *S~plan,\ j~* and *S~interest,\ j~*, and Choosing the Current Visit Target {#sec6dot2dot2-sensors-15-05344}

In order to decide which direction a shopper agent would like to go, we need to know which path segments *j* plans to visit. These path segments are visit targets for *j*, and *j* will visit these path segments one by one. Here we use *S~plan~*~,\ *j*~ to represent the set of path segments that *j* plans to visit, and use *S~interest,\ j~* to represent the set of path segments that *j* feels interested in. According to the item-segment table *IST*, we can derive *S~plan~*~,\ *j*~ by mapping each item in *L~plan~*~,*j*~ to path segments where this item is sold. Similarly, *S~interest,\ j~* also can be derived according to *IST* and *L~interest~*~,*j*~.

*Definition 16.* Given a path graph *G*, suppose a shopper *j* is at terminal point *v*, and the start terminal point and the end terminal point of path segment *s* are *s*.*b* and *s*.*e* respectively. Then the distance between the shopper *j* and the segment *s* is defined as below: where function *shortest_path_length*(·, •) means length of the shortest path between two terminal points in *G*, and function min(·, •) represents the minimal one of two values. In the above definition, length of the shortest path between two terminal points in *G* can be obtained using well-known Dijkstra's algorithm \[[@B43-sensors-15-05344],[@B44-sensors-15-05344]\]. Thus, based on the definition of distance between a shopper and a path segment, we simply use the following method to decide the current visit target.

*Method 1 (deciding the visiting target).* For a shopper *j*, among the elements of *S~plan,\ j~*, the nearest path segment is regarded as the current visit target. If *S~plan,\ j~* is empty, "checkout" becomes the moving target. The current visit target remains unchanged until the current visit target has been visited and *S~plan,\ j~* is updated.

6.3. Step 3. Generation of a Shopping Transaction Path
------------------------------------------------------

The production of a shopping transaction path can be regarded as a repetitive process of deciding which path segment *s~i~* (*i* = 1,2,...,*n*) should be chosen as the next step, and generating unit time per unit length spent in *s~i~* (say *t~i~*) and the itemset purchased in *s~i~* (say *T~i~*).

### 6.3.1. Decision on the Next Path Segment

For simplicity, we suppose the walking process of a shopper *j* is as follows: first, *j* selects a visit target, and then he/she walks along the shortest path to the visit target. When he/she reaches the current visit target, he/she needs to decide the next visit target. The process is repeated, until he/she finishes his/her shopping and arrives at "checkout". Thus, we have the following method for deciding the next path segment.

*Method 2 (deciding the next path segment)*. Given a path graph *G*, if a shopper *j* hasn't reached the current visit target, the next section along the shortest path to the current visit target is selected as the next path segment for *j*. If *j* arrives at the current visit target, he/she considers and decides the next visit target. Then, the next path segment along the shortest path to the next visit target is chosen as the next section.

In this method, the shortest path to a visit target can be obtained by popular Dijkstra's algorithm \[[@B43-sensors-15-05344],[@B44-sensors-15-05344]\].

### 6.3.2. Sub-Step 3.2 Generating *t~i~* and *T~i~*, and Updating *L~plan,\ j~*, *L~interest,\ j~*, *S~plan,\ j~*, *S~interest,\ j~* and Visiting Target

1.  Generating *t~i~* and *T~i~*

For a shopper *j*, *t~i~* is the quotient of time spent in *s~i~* (say *time~s~i~,\ j~*) divided by the length of *s~i~* (say *s~i~*.*l*). *time~si~*~,\ *j*~ consists two parts: time spent for walking in *s~i~* (say *time~walking,\ s~i~,j~*) and time spent for shopping in *s~i~* (say *time~shopping,\ s~i~,\ j~*). *time~walking,\ s~i~,\ j~* can be computed as below: where *speed~j~* is *j*'s actual moving speed.

For simplicity, the value of *time~shopping,\ s~i~,\ j~* depends on whether *j* feels interested in *s~i~* (that is *s~i~ ∈ S~interest~*~,\ *j*~) or not, and is computed as below: $$\textit{time}_{\textit{shopping},~s,~j} = \left\{ \begin{matrix}
{\sum\limits_{\forall i_{\textit{item}},i_{\textit{item}} \in L_{\textit{interest},j}˄i_{\textit{item}} \in \Gamma_{S_{i}}}{\textit{ShoppingTime}(i_{\textit{item}})~\text{if}~S_{i}~ \in ~S_{\textit{interest},j}}} \\
{0\,\,\,\,\,\,\,\,\,\,\,\,\,\text{if}~S_{i} \notin ~S_{\textit{interest},j}} \\
\end{matrix} \right.$$ where *Γ~s~i~~* is the itemset sold in *s~i~* and can be obtained from *SIT*.

For *s~i~*, *T~i~* simply equals to the set of items that belong to both *L~plan,\ j~* and *Γ~s~i~~*.

2.  Updating *L~plan,\ j~*, *L~interest,\ j~*, *S~plan,\ j~*, *S~interest,\ j~* and visiting target

If *s~i~* ∉ *S~interest,\ j~*, nothing needs to be updated. Otherwise, since *s~i~* has been visited, it should be deleted from *S~interest,\ j~*. For the reason that *T~i~* has been purchased at *s~i~*, items in *T~i~* need to be removed from *L~plan,j~* and *L~interest~*. If *s~i~* ∉ *S~plan,\ j~*, *s~i~* also should be pruned from *S~plan,\ j~*, and the visiting target should be updated further using Method 1, which is given in [Section 6.2.2](#sec6dot2dot2-sensors-15-05344){ref-type="sec"}.

6.4. Step 4. Attaching Extra Loop Repeat Patterns and Palindrome-Contained Patterns
-----------------------------------------------------------------------------------

Producing extra loop repeat patterns and palindrome-contained patterns are exactly the reverse processes of simplifying these two patterns which are presented in Definitions 12 and 13. The methods for producing a loop repeat pattern and a palindrome-contained pattern are described below:

*Method 3 (producing a loop repeat pattern)*. A shopping transaction path, *i.e.*, *STP~prefix~*→*STP~combine~*→*STP~suffix~*, can be transformed to any *STP~prefix~*→*STP*~1~→*STP*~2~→...→ *STP~n~*→*STP~suffix~*, where *STP~combine~=*\<(*s*~1~, *t*~1~, *T*~1~), (*s*~2~, *t*~2~, *T*~2~),..., (*s~λ~*, *t~λ~*, *T~λ~*)\>, *STP~i~* = \<(*s*~1~, *t*~1,*i*~, *T*~1,*i*~), (*s*~2~, *t*~2,*i*~, *T*~2,*i*~),..., (*s~λ~*, *t~λ~*~,*i*~, *T~λ~*~,*i*~)\>, *STP~combine~* and all *STP~i~* (*i* = 1,...,*n*) share the same navigation pattern (say Trans(*TSP*) = \<*s*~1~, *s*~2~, ..., *s~λ~*\>), only if the following equations are satisfied: $$t_{j} = t_{walking} + \sum\limits_{i = 1}^{n}t_{purchasing}(i,j)~(j = 1,\ldots,\lambda)$$ $$T_{j} = \underset{i = 1}{\overset{m}{\cup}}T_{j,i}~(j = 1,\ldots,\lambda)$$ where *t*~walking~ is the smallest value of time spent per unit length in this shopping transaction path.

*Method 4 (producing a palindrome-contained pattern)*. A shopping transaction path, *i.e.*, *STP~prefix~*→*STP~combine~*→*STP~suffix~*, can be transformed to any *STP~prefix~*→*STP~1~*→*STP~2~*→*STP~3~*→*STP~suffix~*, where *STP~combine~* = \<(*s*~1~, *t*~1~, *T*~1~), (*s*~2~,*t*~2~, *T*~2~),..., (*s~λ~*, *t~λ~*, *T~λ~*)\>, *STP~i~* = \<(*s*~1~,*t*~1,*i*~, *T*~1,*i*~), (*s*~2~, *t*~2,*i*~, *T*~2,*i*~),..., (*s~λ~*, *t~λ,i~*, *T~λ,i~*)\> (*i* = 1, 3), *STP~2~* = \<(*s~λ,reverse~*, *t~λ~*~,2~, *T~λ~*~,2~), (*s~λ~*~-1,*reverse*~, *t~λ~*~-1,2~, *T~λ~*~-1,2~), ..., (*s*~1*,reverse*~, *t*~1,2~, *T*~1,2~)\>, only if the following equations are satisfied: $$t_{j} = t_{walking} + \sum\limits_{i = 1}^{3}t_{purchasing}~(j,i)~(j = 1,\ldots,\lambda)$$ $$T_{j} = \underset{i = 1}{\overset{3}{\cup}}t_{j,i}~(j = 1,\ldots,\lambda)$$ where *t*~walking~ is the smallest value of time spent per unit length in this shopping transaction path. Therefore, in order to produce a loop repeat pattern or palindrome-contained pattern, firstly, we randomly choose a fragment of shopping transaction path as *STP~combine~*. And then, transform *STP~combine~* according to Method 3 or Method 4. Multiple loop repeat patterns and palindrome-contained patterns can be produced after executing the above process multiple times.

For a database of shopping transaction paths *D*, five parameters are introduced here: the number of loop repeat patterns (say *n~LRP~*), the number of palindrome-contained patterns (say *n~PCP~*), the average number of path segments in *STP~combine~* for loop repeat patterns (say *λ~LRP~*), the average number of path segments in *STP~combine~* for palindrome-contained patterns (say *λ~PCP~*), the average repeat times in loop repeat patterns (say *n~repeat~*).

7. Experimental Results {#sec7-sensors-15-05344}
=======================

To assess the performance of the algorithm of identifying the mainstream shopping transaction paths and PFNP-forest algorithm, we conducted several experiments on a PC with a 3.00GHz Intel Core™ 2 Duo E8400 CPU (Santa Clara, CA, USA) and 4GB main memory, running Windows 7 Enterprise Edition. All algorithms are implemented using VC++ 2010. In these experiments, we establish a path graph, which has 159 terminal points and 554 path segments, as an example to generate shopping transaction paths. Without specific explanations, Default values of various parameters used in our simulations are summarized in [Table 5](#sensors-15-05344-t005){ref-type="table"}. Since the kernel parts of identifying mainstreams are Function LRP_Filtering() (which is used for filtering loop repeat patterns) and Function PCP_Filtering() (which is for filtering palindrome-contained patterns), we test the performance of these two functions.

sensors-15-05344-t005_Table 5

###### 

Default values of various parameters used in our simulations.

  Parameter                    Value   Parameter                            Value   Parameter     Value
  ---------------------------- ------- ------------------------------------ ------- ------------- -------
  *n~terminal_points~*         159     *lower_bound~nplan,\ j~*             1       *\|D\|*       1000
  *n~path_segments~*           554     *upper_bound~nplan,\ j~*             20      *n~repeat~*   3
  *n~items~*                   3000    *lower_bound~nextra_interest,\ j~*   0       *n~LRP~*      1000
  *μ~speed_normal~*            0.6     *upper_bound~nextra_interest,\ j~*   8       *n~PCP~*      1000
  *σ~speed_normal~*            0.1     *μ~ShoppingTime~(i~item,k~)*         1       *λ~LRP~*      3
  *σ~PreceivedTimdPressure~*   0.1     *σ~ShoppingTime~(i~item,k~)*         0.5     *λ~PCP~*      3

7.1. Variations of n~LRP~ (or n~PCP~)
-------------------------------------

Firstly, variations of different execution times with different values of *n~LRP~* (or *n~PCP~*) are evaluated and compared. We run the simulation (without Step 4) 1000 times and obtain an original database of shopping transaction paths with *\|D\|* = 1000 and *L* = 57.4. And then, extra 1000, 2000, 3000, 4000, 5000 and 6000 loop repeat patterns (or palindrome-contained patterns) are attached to the original database with *λ~LRP~* = 3, *λ~PCP~* = 3, and *n~repeat~* = 3, respectively, using Step 4 in simulation. The execution time of Function LRP_Filtering() and Function PCP_Filtering() in response to different *n~LRP~* (or *n~PCP~*) are shown in [Figure 9](#sensors-15-05344-f009){ref-type="fig"}.

![Execution time in response to changes in different *n~LRP~* (or *n~PCP~*).](sensors-15-05344-g009){#sensors-15-05344-f009}

We can find that the execution time of Function LRP_Filtering() is about three times that of Function PCP_Filtering() for the same n~LRP~ (or n~PCP~). Both of them increase linearly with the increase of n~LRP~ (or n~PCP~) and have a good scalability.

7.2. Variations of *λ~LRP~* (or *λ~PCP~*)
-----------------------------------------

Secondly, we test the scalability of these two functions with the increasing of parameter *λ~LRP~* (or *λ~PCP~*). Similarly, we obtain the original database of shopping transaction paths with *\|D\|* = 1000 and *L* = 57.4 by running the simulation (without Step 4) 1000 times. Then extra 1000 loop repeat patterns (or palindrome-contained patterns), whose *λ~LRP~* (or *λ~PCP~*) is 2, 3, 4, 5, 6, 7 and 8, are attached to the original database respectively. The impact of *λ~LRP~* and *λ~PCP~* to the execute time is shown in [Figure 10](#sensors-15-05344-f010){ref-type="fig"}. We can find that both these two functions have a relatively stable execution time with the increase of *λ~LRP~* (or *λ~PCP~*).

![Execution time in response to changes in different *λ~LRP~* (or *λ~PCP~*).](sensors-15-05344-g010){#sensors-15-05344-f010}

7.3. Variations of \|D\|
------------------------

Thirdly, the impact of Variations of *\|D\|* on the execution time is examined. We run the simulation (without Step 4) 500, 1000, 1500, 2000, 2500, 3000 times, respectively, and obtain the corresponding databases of shopping transaction paths. The values of *L* of these databases are 57.7, 57.4, 57.0, 56.9, 56.9 and 57.0, respectively, which are approximately 57. Then, an extra one loop repeat pattern (or palindrome-contained pattern) with *λ~LRP~* = *λ~PCP~* = 3 and *n~repeat~* = 3 is attached to each shopping transaction path of these databases by using Step 4 in the simulator. The experimental results are shown in [Figure 11](#sensors-15-05344-f011){ref-type="fig"}. It is obvious that the execution time of these two functions increases with the increase of *\|D\|*, and both of them have a good scalability.

![Execution time in response to changes in different *\|D\|*.](sensors-15-05344-g011){#sensors-15-05344-f011}

7.4. Variations of L
--------------------

The fourth test examines the execution performance of these two functions with varying *L*. To obtain different databases of shopping transaction paths with different *L*, we set the value of the pair (*lower_bound~nplan,\ j~*, *upper_bound~nplan,\ j~*) to (1, 1), (1, 8), (1, 18), (5, 25), (12, 30) and (20, 36), and running the simulation (without Step 4) 1000 times respectively. Thus we generate six databases of shopping transaction paths whose *L* is 17.4, 35.7, 53.1, 71.1, 89.5 and 105.0, respectively. The difference between successive values of these *L* is approximately 18. Then, we test Function LRP_Filtering() and Function PCP_Filtering() on these databases, and the experimental results are given in [Figure 12](#sensors-15-05344-f012){ref-type="fig"}. We can find that the execution time of these two functions increases in a linear manner, and both of these two functions show a good scalability with the increase of *L*.

![Execution time in response to changes in different *L*.](sensors-15-05344-g012){#sensors-15-05344-f012}

7.5. Variations of n~repeat~
----------------------------

Since only Function LRP_Filtering() has the parameter *n~repeat~*, here we test the impact of variations of *n~repeat~* on the execution time of Function LRP_Filtering(). After obtaining the original database of shopping transaction paths with *\|D\|* = 1000 and *L* = 57.4, 1000 loop repeat patterns with varying *n~repeat~* (which are 2, 3, 4, 5, 6) are attached to the original database respectively, and then the corresponding databases with varying *n~repeat~* are obtained. We test the varying execution time for these databases and show the experimental results in [Figure 13](#sensors-15-05344-f013){ref-type="fig"}. We find that the execution time is almost stable with different *n~repeat~*. This result also can be obtained by analysing Function LRP_Filtering(). Since varying *n~repeat~* will not change the number of repeat loop patterns that are found, the execution times will not change too much for different *n~repeat~*.

![Execution time in response to changes in different *n~repeat~*.](sensors-15-05344-g013){#sensors-15-05344-f013}

8. Contributions toward a Real Supermarket Scenario {#sec8-sensors-15-05344}
===================================================

The contributions of the framework towards a real supermarket scenario include the following aspects: (1) It provides a feasible way for retail practitioners to record customers' shopping trajectories associated with their purchasing behaviors using RFID technology; (2) It designs a path graph schema with the support of a segment-item table and item-segment table, which can be used for the mapping between the physical world and the semantic cyber space. After the mapping, the data semantics can be understood by retail practitioners; (3) It offers a practical approach for preprocessing raw in-store RFID data, which contains five steps: data ordering and compression, data merging and anomaly detection, segment extraction, segment reassembling and extracting mainstream shopping transaction paths. Based on this approach, the raw data will become reliable and clean for retail practitioners; (4) It aims at mining actionable navigation patterns from a combination of customers' shopping paths and their purchasing behavior data. Actionable knowledge is quite useful for decision making \[[@B24-sensors-15-05344],[@B25-sensors-15-05344]\]. For example, we firstly cluster trajectories according to the duration of customers' stays in the store. Then, practitioners can intuitively explore long "stock-up" trajectories where a long time is spent and many different types of products are purchased by customers. Some interesting patterns may be discovered by data mining algorithms, e.g., shoppers of these "stock-up" trajectories tend to frequently walk through a certain popular spot. Thus, decision-makers may consider offering active services, such as product recommendations and advertising, in that spot.

9. Conclusions {#sec9-sensors-15-05344}
==============

In this paper, we use the retail industry as an example to explore the potential of RFID technology for indoor mapping and navigation. In a supermarket scenario, RFID provides the ability to interact with items (*i.e.*, transport carts, trolleys, kegs and valuable products) without physical contact. Thus, item-level RFID infrastructures not only provide item handling efficiency, but also offer a promising way to capture customers' in-store behavior data and then gain insight into these data using data mining technology.

In this context, we provide a framework for mining actionable navigation patterns by combining RFID in-door mapping and data mining techniques. In the framework, multi-source in-door RFID data (*i.e.*, shopping path data and RFID-supported customers' purchasing behavior data) is integrated together for in-depth customers' behavior analytics. The framework consists of four modules: (1) mapping from the physical space to the cyber space; (2) data preprocessing; (3) data mining mechanism; and (4) knowledge understanding and utilization. Among them, the kernel part, *i.e.*, the scheme of extracting mainstream shopping transaction paths, is discussed in detail. The scheme of identifying mainstreams aims at catching the mainstream path sequences while discarding unnecessary redundant and repeated details, and is quite different from the scheme of extracting maximal forward reference. Two types of redundant patterns, *i.e.*, loop repeat pattern and palindrome-contained pattern, are recognized, and the corresponding algorithms are proposed and evaluated. Experimental results show that the algorithm is efficient and scalable for filtering these redundant patterns. On the whole, this work builds a bridge between indoor positioning and advanced data mining technologies, and provides a feasible way to study customers' shopping behaviors via multi-source RFID data.

We would like to thank Longbing Cao (University of Technology, Sydney) for helpful suggestions. This work is supported by National Natural Science Foundation of China (No. 71271191), the National Science & Technology Pillar Program during the 12th Five-year Plan Period of China (2012BAF12B11), Zhejiang Provincial Natural Science Foundation of China (No. Y1110960) and Scientific Research Foundation for the Returned Overseas Chinese Scholars (Ministry of Human Resources and Social Security of China, 2013).

Bin Shen has initiated the idea of the work, conducted the research design and implemented the research. Qiuhua Zheng, Xingsen Li and Libo Xu have participated in concept, algorithm design and implementation and commented on the manuscript. Bin Shen has written the manuscript. The final manuscript has been approved by all authors.

The authors declare no conflict of interest.
