CN112434118B

CN112434118B - Index structure, creation method, system, query method and system

Info

Publication number: CN112434118B
Application number: CN202011254329.2A
Authority: CN
Inventors: 李艳红; 张望; 冯禹鹤
Original assignee: South Central University for Nationalities
Current assignee: South Central Minzu University
Priority date: 2020-11-11
Filing date: 2020-11-11
Publication date: 2024-02-13
Anticipated expiration: 2040-11-11
Also published as: CN112434118A

Abstract

The invention discloses an index structure, a creating method, a creating system, a query method and a query system, and relates to the field of space keyword query. The index structure provided by the invention comprises: a first layer for storing static objects in a base unit corresponding to a leaf node; and the second layer is used for taking the leaf nodes of the first layer as inlets, and inserting the nodes created in the second layer into the moving objects. The query method comprises the following steps: if the leaf node R of the first layer of the index structure is in the case of inquiring the moving object expected by the user _i And does not intersect the refined query result area, R is pruned at a first and/or second level of the index structure _i And the search space of its sub-nodes; and calculating the probability of the occurrence of the user expected object in the corresponding basic unit in the nodes of the second layer of the index structure within a period of time, and reducing unnecessary searching space of the nodes and groups according to the normal distribution principle. The method and the device can solve the Top-k WSKM query problem of the mobile object.

Description

Index structure, creation method, system, query method and system

Technical Field

The invention relates to the field of space keyword query, in particular to an index structure, a creating method, a system, a query method and a system.

Background

With the widespread use of mobile devices and the popularity of LBS (Location Based Services ), a large number of mobile objects with spatial text features have been generated. Top-k (find the Top k name in a set, k is a positive integer) SK (Spatial key) query is one of the most important query forms in LBS, and has been widely studied in academia and industry. Top-k SK queries use spatial coordinates, a set of keywords, and k values as query requirements, and return k objects that best match the query requirements.

In some cases, some user-desired objects (missing objects) may not appear in the query result set when the user initiates a Top-k SK query. The user may want why these objects have disappeared, whether other unknown related objects have disappeared, or even have a question about the entire query result. It is therefore necessary to explain the cause of these missing intended objects and to provide a refined query that contains all the missing objects and the original query result objects.

For example: one day is very hot and john thirsty in his company, desiring a cup of milk tea. He then begins to query his company for top three milky tea stores. After receiving the query results, he unexpectedly found that neither a good mobile milk tea booth nor a regular milk tea booth was in the result set. John wants to know why he wants the object queried missing and how to get a refined query keyword so that all missing stores and other potentially better options appear in the refined query result set.

The problem of John in the above example is called the "Why-not" (why it is not) problem. In contrast to other methods of answering the "Why-not" question, such as operation recognition, ontologies, and database modification, the query optimization method can retrieve all missing objects for the user by adjusting the original query requirements. Chen et al answer the question of "Why-not" in the spatial key Top-k query by adjusting the weights between spatial correlation and text similarity. Later, zhao et al, wang et al, and Zheng et al processed the "Why-not" question in the geo-social space keyword query, the SPARQL query, and the group query, respectively.

However, existing research has focused mainly on the "Why-not" problem in Top-k SK queries for static objects.

Top-k space keyword queries for moving objects return moving or static Top-k objects according to a ranking function that comprehensively considers the spatial distance and text similarity between the query and the moving object. When a user initiates a Top-kSK (which may also be referred to as Top-k SKM) query of a mobile object using some unreasonable query requirements, some mobile objects (which may be referred to as missing objects) that the user wishes may not appear in the query result set, why they do not appear, which is referred to as a "Why-not" problem in SK queries for mobile objects, which is also referred to as Top-k WSKM queries.

In the process of implementing the present invention, the inventor finds that at least the following problems exist in the prior art:

there are four factors that make it more difficult to answer the "Why-not" (Top-k WSKM) question on a moving object Top-k space keyword query:

first, it is a challenge how to reasonably define the movement pattern of a moving object, such as the movement direction and the movement speed, that different moving objects have different movement patterns.

Second, the probability that a moving object appears in a region at a certain moment is a continuous variable, and how to build probability density functions to calculate the probability that a moving object appears in a region within a period of time is also a considerable problem.

Third, during the refined query processing, some original query result objects and missing objects may leave the query point, and it is also a considerable problem how to prune the search space as much as possible while ensuring that these moving objects are not pruned.

Finally, a large number of objects move in the system, meaning that there are often insertions and deletions of moving objects in the index before a refined query is performed, which is time consuming, but the user needs to get the query results as soon as possible, which is a contradiction.

The applicant has not found research results on the "Why-not" problem in Top-k space keyword queries (Top-k WSKM queries) for moving objects.

Disclosure of Invention

The purpose of the present application is to overcome the shortcomings of the above background art, and provide an index structure, a method and a system for creating the same, and a query method and a system for querying the same, which can solve the problem of "Why-not" in the Top-k space keyword query of a mobile object (i.e. Top-k WSKM query).

In a first aspect, there is provided an index structure comprising:

a first layer for: storing the static object in a basic unit corresponding to the leaf node;

a second layer for: the leaf nodes of the first layer are taken as entries, and the nodes created in the second layer are inserted into the moving object.

On the basis of the technical scheme, the search space of the first layer of the index structure is divided into a plurality of basic units, and all static objects in the search space are indexed by using a quadtree.

On the basis of the technical scheme, the nodes of the second layer of the index structure store information of the mobile object, wherein the information comprises object identification, object positions, object keywords and the probability of the object in a basic unit corresponding to the nodes in a period of time.

On the basis of the technical scheme, the nodes of the second layer of the index structure are distributed into a plurality of groups according to the distance between the nodes and the groups, and each group stores the following information: group identity, group location and group pointer to its neighboring group.

On the basis of the technical scheme, the distance between any two objects in the group does not exceed the length of the group, and the length of the group is calculated according to the position of the group.

In a second aspect, there is provided a method of creating an index structure, comprising the steps of:

determining a leaf node used for storing the static object in a first layer of an index structure serving as an insertion entry, and inserting the static object into the leaf node;

a node for storing the moving object is created in a second layer of the index structure according to a node id different from the leaf node in the first layer and the same node position information, and the moving object is inserted into the node.

In a third aspect, there is provided a system for creating an index structure, comprising:

an inlet determination unit for: determining a leaf node used for storing the static object in a first layer of an index structure serving as an insertion entry, and inserting the static object into the leaf node;

a node creation unit configured to: a node for storing the moving object is created in a second layer of the index structure according to a node id different from the leaf node in the first layer and the same node position information, and the moving object is inserted into the node.

In a fourth aspect, a Top-k WSKM query method based on the above index structure is provided, including the following steps:

if the leaf node R of the first layer of the index structure is found when the moving object desired by the user is queried _i Disjoint from refined query result regions, R is cut in the first and/or second layers of the index structure _i And the search space of its sub-nodes.

Based on the technical scheme, the method further comprises the following steps:

the probability that the nodes of the second layer of the index structure have the user expected objects in the corresponding basic units is calculated in a period of time, and unnecessary nodes and search spaces of groups are reduced according to the normal distribution principle.

In a fifth aspect, a Top-k WSKM query system based on the above index structure is provided, including:

a first clipping unit configured to: if the leaf node R of the first layer of the index structure is found when the moving object desired by the user is queried _i Disjoint from refined query result regions, R is cut in the first and/or second layers of the index structure _i And the search space of its sub-nodes;

a second clipping unit configured to: the probability that the nodes of the second layer of the index structure have the user expected objects in the corresponding basic units is calculated in a period of time, and unnecessary nodes and search spaces of groups are reduced according to the normal distribution principle.

Compared with the prior art, the application has the following advantages:

1. the application proposes a Why-not problem for Top-k space keyword queries on moving objects, also known as Top-k WSKM queries. To the best of the applicant's knowledge, this Top-k WSKM query problem was first addressed by the present application.

2. The present application proposes a new index structure (Shadow index structure) to organize text information, spatial information and movement pattern information of objects. By analyzing the movement pattern of a moving object, calculating the probability that the moving object will appear within a certain area over a certain period of time, the Shadow index structure can help the user capture refined queries with minimal costs at the fastest speed.

Drawings

FIG. 1 is a query q and 18 objects o in an embodiment of the invention ₁ To o ₁₈ A schematic of the distribution in the search space.

Fig. 2 is a schematic diagram of a possible trajectory of a moving object from point a to point B in an embodiment of the present invention.

FIG. 3 is a calculation arc in an embodiment of the inventionSchematic drawing of auxiliary line when moving area enclosed by straight line AB.

FIG. 4 is an arc in an embodiment of the inventionThe corresponding half of the circumference angle is schematically related to the sine value.

Fig. 5 is a schematic diagram of a basic unit to which a moving object may move and a position curve to which a different time may move in an embodiment of the present invention.

FIG. 6 is a schematic diagram of the spatial division of FIG. 1 using a Shadow index structure in accordance with an embodiment of the present invention.

FIG. 7 is a schematic diagram of a Shadow index structure in accordance with an embodiment of the present invention.

Detailed Description

Note that: in the application, "Why-not Top-k space keyword query on a moving object" and "Why-not' problem in Top-k space keyword query of a moving object" refer to the same meaning, which is simply called: "Top-k WSKM query"; and "Top-k space keyword query of moving object", simply referred to as: "Top-k SKM query", the two are simply just one "W" difference, this "W" representing "Why-not".

Aiming at the problem of 'Why-not' (Top-k WSKM query) in the mobile object Top-k SKM query, the embodiment of the application provides a two-layer index structure named Shadow, which comprises the following steps:

The embodiment of the application also provides a method for creating the Shadow index structure, which comprises the following steps:

determining a leaf node for storing the static object in the first layer of the Shadow index structure as an insertion entry, and inserting the static object into the leaf node;

and creating a node for storing the mobile object in a second layer of the Shadow index structure according to the node id different from the leaf node in the first layer and the same node position information, and inserting the mobile object into the node.

The embodiment of the application also provides a system for creating the Shadow index structure, which comprises the following steps:

an inlet determination unit for: determining a leaf node for storing the static object in the first layer of the Shadow index structure as an insertion entry, and inserting the static object into the leaf node;

a node creation unit configured to: and creating a node for storing the mobile object in a second layer of the Shadow index structure according to the node id different from the leaf node in the first layer and the same node position information, and inserting the mobile object into the node.

As a preferred embodiment, the search space of the first layer of the Shadow index structure is divided into a number of base units, and all static objects in the search space are indexed using a quadtree.

As a preferred embodiment, the nodes of the second layer of the Shadow index structure store information of moving objects, including object identification, object location, object keywords, and probability of an object occurring in the base unit corresponding to the node over a period of time.

As a preferred embodiment, the nodes of the second layer of the Shadow index structure are assigned into groups according to their distance from the group, each group storing the following information: group identity, group location and group pointer to its neighboring group. The distance between any two objects in the group does not exceed the length of the group, which is calculated from the group position.

The embodiment of the application also provides a Top-kWSKM query method based on the Shadow index structure, which comprises the following steps:

if leaf node R of the first layer of the Shadow index structure is in the process of querying the mobile object expected by the user _i Disjoint from refined query result regions, R is cut in the first and/or second layers of the Shadow index structure _i And the search space of its sub-nodes;

and calculating the probability that the nodes of the second layer of the Shadow index structure have the user expected objects in the corresponding basic units within a period of time, and reducing unnecessary nodes and search spaces of groups according to a normal distribution principle.

The embodiment of the application also provides a Top-kWSKM query system based on the Shadow index structure, which comprises:

a first clipping unit configured to: if leaf node R of the first layer of the Shadow index structure is in the process of querying the mobile object expected by the user _i Disjoint from refined query result regions, R is cut in the first and/or second layers of the Shadow index structure _i And the search space of its sub-nodes;

a second clipping unit configured to: and calculating the probability that the nodes of the second layer of the Shadow index structure have the user expected objects in the corresponding basic units within a period of time, and reducing unnecessary nodes and search spaces of groups according to a normal distribution principle.

The present application first defines a movement pattern of a moving object. Assuming that a probability density of a moving object appearing at a certain point in a certain area at a given time, the probability of the moving object appearing in the area at a certain point in time and for a certain period of time can be calculated, respectively. The method constructs the Why-not problem (Top-k WSKM query) of the Top-k space keyword query on the moving object, and provides a cost model to measure the modification degree of the refined query relative to the original query, so that the refined query with the minimum modification cost is obtained.

In order to effectively process Top-k WSKM queries, the application provides a three-phase frame-based query processing method.

The first stage is to generate some promising refined queries with different query requirements and filter out unwanted refined queries before executing any promising refined queries.

The second stage is to reduce as much as possible the irrelevant search space in the first layer of the Shadow index structure based on the spatial clipping technique and to capture as fast as possible the promising moving objects in the second layer of the Shadow index structure based on the probability clipping technique.

The third stage is to determine which promising refined queries will be returned to the user.

The relevant background, problems and definitions are first described below.

The application gives some definitions and formally defines the Why-not problem of Top-k space keyword queries on moving objects, abbreviated as: top-k WSKM query.

Table 1 summarizes the symbols commonly used for Top-k WSKM queries and their meanings.

TABLE 1 Top-k WSKM query commonly used symbol table

The Top-k space keyword query (Top-k SKM query) on a moving object is described below.

In existing correlation work, a spatial text object (simply referred to as an object) is typically defined as o= (o.loc, o.doc), where o.loc is a spatial point and o.doc is a set of keywords. In reality, however, the objects are not always stationary and they may move continuously. Moving object o ^m Usually has aFixed movement characteristics, such as: maximum velocity v _max (o ^m ) Minimum velocity v _min (o ^m ) And the actual velocity v at time t ^t (o ^m ). These properties are called object o ^m Mobility MA at time t ^t (o ^m ) Is defined as (v) _max (o ^m ),v _min (o ^m ),v ^t (o ^m ))。

Note that: in the real world, moving objects typically have their destination, so the present application assumes that each moving object moves toward its destination without changing direction or returning.

Thus, given a spatial point o.loc, a set of keywords o.doc and a mobility capability MA ^t (O)), object O ε O can be represented as o= (o.loc, o.doc, MA ^t (o))。

Note that: when MA ^t (o _i ) When empty, object o _i Is static.

Given a query point q.loc, a keyword set q.doc, and two values α and k, then the Top-k space keyword query (Top-k SKM query) q= < q loc, q.doc, α, k > of the moving object retrieves k best objects from the object set O according to a ranking function that comprehensively considers the spatial distance and text similarity between query q and object O, where α is a smoothing parameter that satisfies 0.ltoreq.α.ltoreq.1.

The present application uses a widely used ranking function to measure similarity between query q and object o as follows:

Rank(q,o)＝α*(1-SD(o,q))+(1-α)*ST(o,q)(1)

where SD (o, q) is the normalized spatial distance between query q and object o, and ST (o, q) is the normalized text similarity between query q and object o.

Wherein D is _E (q, o) is the Euclidean distance between query q and object o, maxD _E Representing any two of the object sets OMaximum distance between individual objects.

Examples are illustrated. Referring to FIG. 1, a query q and 18 objects o are distributed in a search space ₁ To o ₁₈ Referring to fig. 1, normalized spatial distance and text similarity information between query q and each object is shown, alpha is a smoothing parameter satisfying 0.ltoreq.alpha.ltoreq.1, when a user starts a Top-3 SKM query, alpha=0.5 is used as input, object o is returned ₂ 、o ₅ And o ₁₃ As a result of the query, these objects are ranked higher than other objects.

The Why-not problem on the mobile object Top-k space keyword query, top-k WSKM query for short, is described below.

When a user initiates a space keyword Top-k query (Top-k SKM query) of a moving object, q= (loc, doc, k, α), k objects are returned to form an original query result set ^O R is defined as the formula. If certain query parameters are incorrectly set in a query, one or more user-desired objects, referred to as missing objects, may accidentally disappear. The present application represents missing object sets as ^m O。

In the existing study of the problem "Why-not" (why it is not) all objects in O are considered static objects. The model of the application can directly deal with the simple condition, directly set the mobile capacity MAt (o) to be empty, and the corresponding refined query result set is called a static refined query result set ^s R。

The user obtains the original result set ^O R＝{o ₂ ,o ₅ ,o ₁₃ ' set up ^m O＝{o ₄ ,o ₉ }. If all of the objects in fig. 1 are static, then existing methods can be used to return a refined query q= (loc, doc,7,0.6) to the user to arrive at a static refined query result set ^s R＝{o ₂ ,o ₅ ,o ₁₃ ,o ₄ ,o ₃ ,o ₈ ,o ₉ }。

However, some objects often move continuously, and existing methods cannot directly address the "Why-not" problem in Top-kSKM queries. For this reason, the present application focuses on the Why-not problem of the mobile object Top-k space keyword query, which is abbreviated as Top-k WSKM query.

Note that: in this application, only k and α are adjusted to capture the inclusion ^o R and ^m refined query result set of O ^r R, some of which are moving objects.

For ease of expression, the present application first gives the following definitions.

Definition 1.(Original Query Result Area,OA for short).

Given a Top-k SKM query q＝(loc,doc,k,a)with a query result set ^o R,there is an object o _i ∈ ^o R,d(q,o)≤d(q,o _i ).Then the original query result area can be defined as a circular area with the query point q.loc as the center and d(q,o _i )as the radius.

Definition 1: the original query result area (Original Query Result Area), OA for short. Given a Top-k WSK query q= (loc, doc, k, α), the query result set is ^o R, there is an object o _i ∈ ^o R, i is a positive integer, for anyd(q,o)≤d(q,o _i ). The original query result area OA is defined as d (q, o) centered on the query point q.loc _i ) Is a circular area of radius.

Definition 2.(Actual Refined Query Result Area,AA for short)

Given a top-k SKM query q with a query result set ^o R and a missing object set ^m O,there are a moving object o ^m _k ∈ ^o R∪ ^m O and a static object o _j ∈ ^o R∪ ^m O,moving objects o ^m ∈ ^o R∪ ^m O–{o ^m _k },we have MAX{v _min (o ^m _k )*(t _t -t _s )+d(q,o ^m _k ),d(q,o _j )}≥v _max (o ^m )*(t _t -t _s )+d(q,o ^m ),where t _s is the starting time of q and t _t is the starting time of the refined query of q.MAX{a,b}returns the maximum value between a and b.Then the actual refined query result area can be defined as a circular area with the query point q.loc as the center and MAX{v _min (o ^m _k )*(t _t -t _s )+d(q,o ^m _k ),d(q,o _j )}as the radius.

Definition 2: the actual refined query result area (Actual Refined Query Result Area), abbreviated AA.

Given a set of results with queries ^o Top-k SKM query q and missing object set for R ^m O, there is a moving object O ^m _k ∈ ^o R∪ ^m O and a static object O _j ∈ ^o R∪ ^m O, j is a positive integer, for any moving object O ^m ∈ ^o R∪ ^m O–{o ^m _k Has MAX { v } _min (o ^m _k )*(t _t -t _s )+d(q,o ^m _k ),d(q,o _j )}≥v _max (o ^m )*(t _t -t _s )+d(q,o ^m ) Wherein t is _s Query the start time of q, t for Top-k SKM _t Where MAX (a, b) is the larger of the returns between a and b, the actual refined query result area AA is defined to be centered around the query point q.loc, MAX { v _min (o ^m _k )*(t _t -t _s )+d(q,o ^m _k ),d(q,o _j ) And is a circular region of radius.

Definition 3: irrelevant Area (IA), abbreviated IA.

Given AA, unrelated areas are defined as areas outside of AA.

For ease of description, the following uses different notationsOriginal query and refined query: original query q= (loc, doc, k ₀ ,α)，k ₀ Is the k value of the original query q, α is the α value of the original query q, the refined query q ' = (loc, doc, k ', α '), k ' is the k value of the refined query q ', and α ' is the α value of the refined query q '.

To measure the refined query q ' = (loc, doc, k ', α ') relative to the original query q= (loc, doc, k) ₀ The modification degree cost (q, q') of α), the following modification cost model is defined:

where β ε (0, 1) is a weight indicating the user's preference for adjusting k or α, Δα _max Is the alpha maximum possible adjustment value and deltak is the k maximum possible adjustment value.

Definition 4.(Why-Not questions on Top-k Spatial Keyword Query over Moving Objects,Top-k WSKM query for short)

Given an original Top-k SKM query q＝(loc,doc,ko,α),an original query result set ^o R and a missing object set ^m O,the Top-k WSKM query returns a refined query q’＝(loc,doc,k’,α’)with the minimum modified cost according to Eqn.(2)and its result set

Definition 4: the Why-not problem of the key word inquiry of the Top-k space of the moving object is called as Top-k WSKM query for short.

Giving an original Top-k SKM query q= (loc, doc, k) ₀ α), a set of original query results ^o R and a missing object set ^m Returning the result set of the O, top-k WSKM query ^r O comprises ^o R∪ ^m O, according to modification cost model equation (2), the refined query q ' = (loc, doc, k ', α ') with the smallest modification cost.

The following describes the moving ability of the moving object.

Each moving objectThere is one destination and its mobility capability. Due to the moving object->With maximum speed->And minimum speed +.>Thus moving object +.>The distance of movement within the Δt time interval isWithin the range.

For ease of discussion, the present application further assumes that a moving object, no matter how fast it moves, will move to its destination and arrive at its destination at a particular point in time.

FIG. 2 shows a possible trajectory of a moving object moving from point A to point B, see FIG. 2Moving from point A to point B if it continues at maximum speed +.>Move, at time t _t Reaching point B, its trajectory is arc AB, denoted +.>Similarly, move object->At a speed +.>When moving, the moving track is a straight line AB.

At a speed ofWhen moving, the moving object +.>The movement at time t is limited to two arcs +.>Within the scope of the enclosure, called +.>Is provided for the movement region of the vehicle.

Note that: t epsilon t _s ,t _t ]And (b)

Therefore, the length of the line segment AB isArc->Is approximately equal to>

The following describes how the area of the moving area is calculated.

FIG. 3 shows a calculated arcAn auxiliary line for the area of the moving area enclosed by the straight line AB, as shown in FIG. 3, the angle γ represents an arc +.>Half of the corresponding circumferential angle, then:

By simplification, it is possible to obtain:

since γ ε (0, pi/2), a value γ can be found ₁ E (1, pi/2) ensure

FIG. 4 shows an arcHalf of the corresponding circumference angle is related to its sine value, see FIG. 4, < >>The area of the moving area of (c) is calculated as follows:

in this way, two arcs can be calculatedIs a formula expression of (2).

Because of space limitations, detailed calculations are not presented here, but are merely shown asAnd->Then->The area of the moving area of (c) can be calculated by another method as follows:

the probability density and probability are described below.

Due to moving objectsIs not fixed, so +.>The position to which it is moved at time t should be on curve l. As is well known, spatial indexing is based on dividing the entire search space into a number of basic units. Thus, for any given spatial index, curve l may appear in one or more base cells.

Assuming that the curve l appears in n basic units at time t, n is a positive integer, called C ₁ ,C ₂ ,…,C _n The parts of the curve that appear in these cells are called l respectively ₁ ,l ₂ ,…,l _n The following steps are:and l _i >0。

If it isThe probability density of a point appearing on curve l at time t is +.>Then->Appear in l _i The probability of a part is:

Note that:

due to moving objectsThe possible positions at different points in time consist of different curves, the intersections of which with the base unit can be obtained, and therefore t can be calculated ₁ To t ₂ The presence of +.>The probability of (2) is:

FIG. 5 shows a moving objectFrom t _s From time to t _t Moving track of time, see FIG. 5, moving object +.>Respectively at t ₁ Time sum t ₂ Appear at the base unit C at the moment ₂ And C ₁ In, at t ₃ Moment, moving object +.>The position curve of (2) appears in the basic unit C ₁ And C ₂ The parts in (a) are respectively l ₁ And l ₂ 。

If l ₁ And l ₂ The probability densities of (a) are the same, assuming thatThen move object +.>Appear in l ₁ The probability of (2) is:moving object->Appear in l ₂ The probability of (2) is:

at different time points t e [ t ] ₂ ,t ₃ ]Moving objectAppears in the base unit C ₁ The probabilities in (a) are different, moving object +.>From t ₂ From time to t ₃ Appear at the base unit C at the moment ₁ The probability of (3) is:

furthermore, the present application may use another method to calculate the time at [ t ] ₁ ,t ₂ ]During which the object is movedThe probability of occurrence in the base unit is briefly described below.

In one aspect, as described above, two arcsCan be calculated and respectively marked as +.>And

on the other hand, the base unit C _i Usually carrying its spatial information, can be organized as a function g (C _i ) According toAnd g (C) _i ) Can calculate the position relation of the moving object +.>Motion trail and basic unit C _i In time period [ t ] ₁ ,t ₂ ]Probability of intersection, i.e.)>And g (C) _i ) Is defined by the intersection area of the two adjacent segments.

The probability distribution function and the normal distribution are described below.

In explaining how to calculate the moving objectAfter a period of probability of appearing in the base unit, the present application gives the probability distribution function as follows:

the probability distribution function can be used in two ways:

1) Given two time points t _i And t _j Wherein t is _s ≤t _i <t _j ≤t _t Can calculate t _i To t _j Probability of occurrence of a moving object in the basic unit during the period;

2) Given a start time t _s If a moving object is desiredThe probability of occurrence in a basic unit is greater than a certain value, a key time point t can be calculated _k So that at t _s By time t, moving object +.>Appear at C _i The probability of (c) is greater than this value, where t e (t _k ,t _t )。

As described above, at time t, curve l is divided into n parts: l (L) ₁ ,l ₂ ,…,l _n Each part has a moving objectProbability of appearing on it. In the same way, the present application can calculate the value at t using equation (3) _i To t _j During which the moving object->Appears in the base unit C ₁ ,C ₂ Probability in …, where t _s ≤t _i <t _j ≤t _t . This means that at t _i To t _j During this time, the probability that each moving object appears in a different base unit is different.

If the missing object is a moving object, the refined query must return it and the different locations and probabilities of its occurrence. Note that the probability that a moving object appears at a point over a period of time is a probability density and has no practical meaning. In an experiment, the present application calculates the probability that a mobile object appears in a base unit, and uses this probability value as the probability that the mobile object appears at any point in the base unit.

However, a discrepancy arises when the probability of a moving object appearing in the base unit is very small and the base unit is very far from the query point for a period of time.

On the one hand, if it is desired to ensure that each refined query captures the moving objects required by the user with 100% probability, it is necessary to access the base unit and other unnecessary search space far from the query point, which takes time.

On the other hand, if the refined query cannot access all the base units where the mobile object appears with a certain probability, then the refined query has a probability that the object desired by the user cannot be retrieved.

To ensure that the probability is as small as possible, and to solve this contradiction, the present application uses the 3 sigma principle of the positive too distribution. With respect to normal distributionWhere μ is the mean, σ is the standard deviation value, and x=μ is the symmetry axis of the image.

The 3 sigma principle of the n-theta distribution is: the probability of the numerical distribution in (μ - σ, μ+σ) was 0.6826, the probability of the numerical distribution in (μ -2σ, μ+2σ) was 0.9544, and the probability of the numerical distribution in (μ -3σ, μ+3σ) was 0.9974. Therefore, it is considered that the value of P (μ -3σ, μ+3σ) is 0.9974, and the value of Y is almost entirely concentrated in the (μ -3σ, μ+3σ) interval, and the possibility of exceeding this range is only less than 0.3%.

The 3σ principle means that a variable x that does not belong to (μ -3σ, μ+3σ) is a small probability event that would not normally occur. Thus, if the object is movedThe sum of the probabilities of occurrence in some of the basic units is greater than P (mu-3 sigma<x.ltoreq.mu+3σ), i.e. 0.9974, then no access to other ones is required>The basic units that occur with a certain probability can be used to filter out unnecessary search space to increase query processing efficiency.

The Top-k WSKM query method based on the Shadow index structure is described below.

The focus is next to design a novel index to efficiently store and process objects, knowing how to calculate the probability that a moving object will appear in a base unit over a period of time, and knowing the fact that a refined query does not need to find the moving object that the user needs with 100% probability. If existing methods are used to hold objects (static or moving) to answer Top-k WSKM queries, it is necessary to first delete or insert moving objects from the index, then update the index accordingly, and finally perform refined queries on the modified index. This has two disadvantages:

1) Time consuming, especially when a large number of moving objects are far from the query point;

2) If moving objects and their information are deleted, inserted, and the index structure is updated, some moving objects may move to other locations during execution of the refined query, which may affect the accuracy of the refined query results.

To overcome these disadvantages, the present application proposes an index structure named Shadow index structure, which is described in detail below.

The Shadow index structure contains two levels. In the first layer, the entire search space is divided into several basic units as described above, and all static objects in the search space are indexed using one quadtree. Leaf nodes in the first layer of the Shadow index structure store static objects in base units corresponding to the leaf nodes. Thus, no matter how the moving object moves, the first layer of the Shadow index structure is not affected.

In the second layer of the Shadow index structure, all moving objects are organized.

Inserting the first moving object into the second layer of the Shadow index structure, comprising the steps of:

first, assuming that the moving object is static, find leaf nodes to be inserted into the first layer of the Shadow index structure;

then, in the second layer of the Shadow index structure, a node is created with a node id different from the leaf node in the first layer and the same node position information;

finally, the mobile object is inserted into the node.

When other mobile objects are to be inserted into the second layer of the Shadow index structure, determining whether the second layer nodes of the Shadow index structure to be inserted exist or not, and if so, only inserting the objects into the nodes; otherwise, a node needs to be built in the second layer of the Shadow index structure, and then the object is inserted into the node.

Note that: if the number of objects in the nodes of the second layer of the Shadow index structure exceeds the maximum capacity of the node, the node needs to be divided into 4 sub-nodes, and the specific method is the same as in the quadtree.

Each node in the second layer of the Shadow index structure stores information about the mobile objects it contains, including object identification o ^m Id, object position o ^m Loc, object keyword o ^m Doc and object o ^m At [ t ] _i ,t _j ]Probability of occurrence in the basic unit corresponding to the node in the time period:

all moving objects are inserted into the second layer of the Shadow index structure, and all nodes of the second layer of the Shadow index structure are distributed into a plurality of groups according to the distance between the nodes and the groups. For each group, the following information is stored: group identification G _a Id, group position G _a Loc and group pointer G to its adjacent group _a P, according to group position G _a Loc calculates the length of the group, and the distance between any two objects in the group does not exceed the group length. Note that: each group has the same upper group length limit. When a group reaches the upper limit of length, no matter how close a node in the second layer of the Shadow index structure is to the group, it is not assigned to the group.

Referring to FIG. 6, FIG. 6 shows the partitioning of all objects of FIG. 1 using the Shadow index structure, with 18 objects o in FIG. 1 ₁ -o ₁₈ Wherein o ₂ 、o ₃ 、o ₉ 、o ₁₀ 、o ₁₈ For moving objects, the rest being static pairsLike a Chinese character.

Referring to FIG. 7, FIG. 7 shows a Shadow index structure built for all of the objects in FIG. 1, each static object being assigned to its base unit, each moving object also finding the corresponding base unit. Note that in this example, it is assumed that at most four objects of information can be held per basic unit.

Referring to fig. 7, a first layer of the Shadow index structure stores information of static objects, and a second layer of the Shadow index structure stores information of moving objects, each leaf node of the first and second layers corresponding to one basic unit in fig. 6.

Due to the moving object o ₉ 、o ₁₀ With static object o ₈ 、o ₁₁ 、o ₁₂ In the same basic unit, it is necessary to first find the storage static object o at the first layer of the Shadow index structure ₈ 、o ₁₁ And o ₁₂ Then creates a node in the second layer of the Shadow index structure to store the mobile object o ₉ And o ₁₀ . From storage of static object o ₈ 、o ₁₁ And o ₁₂ Is directed to store mobile object o ₉ And o ₁₀ As one of the entries into the second layer of the Shadow index structure. Due to the moving object o ₉ And o ₁₀ Storage node a of (a) than moving object o ₂ And o ₃ Is closer to the moving object o ₁₈ Thus assigning a and C to the second group and B to the first group.

Specific steps in creating a Shadow index structure may be referred to algorithm 1.

The inputs to algorithm 1 are an object set O containing static objects and moving objects, a queue Q storing all moving objects, and an upper limit Gl for limiting the group length of the group size _max And outputting a Shadow index structure. The first and second layers of the Shadow index structure are created by commanding lines 4 and 5-12, respectively.

Algorithm 1：Creating Shadow Algorithm

Algorithm 1: shadow index structure creation algorithm:

1.Input:an object set O,a queue Q storing the moving objects,the upper limit Gl _max of group length；

2.Output:Shadow；

3.begin

4. establishing a quadtree for the static object in O to form a 1 st level of a Shadow index structure;

while (Q is not empty) do

6.{o _i ^m ＝Out_Queue(Q)；

7. Let o be _i ^m For static objects, find contains o _i ^m Leaf node R corresponding to the basic unit of (2) _i ；

8.if(R _i With one directed to the second layer node R _i ' pointer), then

{ will o _i ^m Insertion of R _i ’；}

10.else

{ create an R at the second layer _i Pointed node R _i ', and o ^m _i Insertion of R _i ’；}}

12. Grouping all nodes in the second layer to ensure that the length of each group does not exceed Gl _max ；

13. Returning to the Shadow index structure.

The space reduction technique is described below.

The present application introduces several lemmas to effectively cut down unnecessary search space for each refined query q' to be examined. First, the AA (actually refined query result area) defined above is used to cut down unwanted nodes in the first layer of the Shadow index structure.

Lemma 1: node R in the first layer of a given Shadow index structure _i And AA refining query q', if R _i And AA are not intersected, R _i Its sub-nodes willIs cut down.

And (3) proving: let R be _i Containing the result object o _i D (q', o) _i ) Not greater than the radius of AA. Due to R _i Is not intersected with AA, R _i All objects in (a) are not in the range of AA, o _i Nor is it true. Thus, d (q', o) _i ) A radius greater than AA, which contradicts the assumption. Thus, R is _i And its sub-nodes can be safely cut down.

Note that: this clipping technique may also be used to filter unwanted nodes and groups in the second layer of the Shadow index structure. Second, in the second layer of the Shadow index structure, the normal distributed 3σ principle can be utilized to filter unnecessary nodes and groups.

And (4) lemma 2: set of nodes { R in the second layer of a given Shadow index structure ₁ ,R ₂ ，…R _i User desired moving object o _i ^m Occurs with different probabilities within the basic units corresponding to the nodes within a period of time, if the sum of probability values of some nodes in the node set is greater than P (mu-3 sigma) of normal distribution<x.ltoreq.mu+3σ), then in process o _i ^m No access to other nodes and groups is required in the process.

And (3) proving: the proof of this axicon can be directly derived from the normal 3 sigma principle of distribution and is therefore omitted.

The following describes how to answer the "Why-not" question in the Top-k SKM query.

After the original query is executed, some user-desired objects may be missing from the query result set. The main objective of the present application is to obtain a refined query with minimal modification costs, the result set of which contains all the original query result objects and all the missing objects required by the user.

Algorithm 2 in this application presents the processing steps of answering why-not questions (i.e., top-k WSKM queries) in a Top-k SKM query using a Shadow index structure. Since some existing approaches have studied how to adjust the α and k answer the "why-not" problem in the space keyword Top-k query in the case where all objects are static, the present application discusses mainly the part that is different from the existing static algorithms.

The inputs of algorithm 2 are a Shadow index structure, an initial query q= (loc, doc, k, α), a promising refined query set, an actual refined query result area AA, an initial query result set ^O R, a missing object set ^m O, time t for executing the current refining query, start time t _s And end time t _t An optimal refined query q' and its result set are output.

First, the query result set is refined ^r R and the node set RS are set to be empty, and the object meeting the requirements of the refining query and the leaf node of the first layer of the Shadow index structure as the entry of the second layer of the Shadow index structure are respectively stored (line 4). Next, a refined query is fetched from the set of promising refined queries and its cost is calculated. If the cost of a refined query is lower than any other refined query previously executed, the refined query will be executed. Otherwise, execution of the refined query is terminated and the next promising query execution is selected (line 5).

According to lemma 1, irrelevant tree branches and nodes corresponding to the search space without AA intersections in the first layer of the Shadow index structure can be filtered (line 6), and then the set of nodes RS for the promising static objects and leaf nodes containing those objects can be found (line 7). All promising static objects are now captured and then the desired moving object is obtained according to the remaining steps of algorithm 2.

If RS is not null, leaf node R in RS _i Is fetched as an entry to access the nodes and groups in the second layer of the Shadow index structure (using pointers stored on this leaf node). Then at R _i Mobile objects meeting the requirements of the refined query are found in the linked nodes. If the probability value of the occurrence of these objects in the search space corresponding to the nodes is larger than the normal distribution P (mu-3 sigma)<x.ltoreq.mu+3σ), these moving objects are added to ^r R is defined as the formula. If one of the objects is not satisfied, the other nodes in the same group that the node is located in will be accessed first. If necessary, access nodes in other groups near the group until the probability of the object is satisfiedUntil required (lines 8-10).

When RS is empty, calculate ^r The ranking scores of all the objects in R keep k best objects. Finally, return a refined query ^r R。

Algorithm 2: top-k WSKM query algorithm based on Shadow index structure:

Algorithm 2:Shadow Based Algorithm

the Top-k WSKM query algorithm 2 based on the Shadow index structure comprises the following specific contents:

input: shadow, q, a desired refined query set, AA, ^o R, ^m O,t,t _s ,t _t ；

output: best refined query q ' = (loc, doc, k ', a '), ^r R；

3.begin

4.set

5. executing one of the set of desired refined queries at a cost less than any other refined query previously executed;

6. deleting irrelevant nodes of a first layer of a Shadow index structure corresponding to the search space without the AA intersection;

7. searching a promising static object and a node set RS of leaf nodes containing the objects;

while (RS non-null) do

{ remove leaf node R from RS _i And accessing a second layer of the Shadow index structure;

10. find out not to be at ^r The promising moving objects in R and meeting the requirements of refining query are inserted into RS according to the requirements of normal distribution 3 sigma principle; }

11. Calculation of ^r The ordering score of all the objects in R is reserved for Top-k' objects;

12. returnBack q ' = (loc, doc, k ', a '), ^r R。

it will be apparent to those skilled in the art that various modifications and variations can be made to the present invention without departing from the spirit or scope of the invention. Thus, it is intended that the present invention also include such modifications and alterations insofar as they come within the scope of the appended claims or the equivalents thereof.

Claims

1. An indexing structure comprising:

a second layer for: taking a leaf node of a first layer as an entrance, and inserting a moving object into a node created in a second layer;

the search space of the first layer of the index structure is divided into a plurality of basic units, and all static objects in the search space are indexed by using a quadtree;

nodes of the second layer of the index structure store information of the mobile object, wherein the information comprises an object identifier, an object position, an object keyword and the probability of the object appearing in a basic unit corresponding to the node in a period of time;

nodes of the second layer of the index structure are allocated into groups according to their distance from the group, each group storing the following information: group identity, group location and group pointer to its neighboring group;

the distance between any two objects in the group does not exceed the length of the group, which is calculated from the group position.

2. A method of creating an index structure, comprising the steps of:

creating a node for storing the moving object in a second layer of the index structure according to a node id different from the leaf node in the first layer and the same node position information, and inserting the moving object into the node;

3. A system for creating an index structure, comprising:

a node creation unit configured to: creating a node for storing the moving object in a second layer of the index structure according to a node id different from the leaf node in the first layer and the same node position information, and inserting the moving object into the node;

4. A Top-k WSKM query method based on the index structure of claim 1, comprising the steps of:

5. The method of claim 4, further comprising the step of:

6. A Top-k WSKM query system based on the indexing structure of claim 1, comprising: