CN102646118B - Data indexing method and device - Google Patents

Abstract

The invention provides a data indexing method and device and relates to the field of data management, and the method and the device are used for solving the problem that the traditional indexing technology can not meet the needs of large data retrieval. The method comprises the following steps: creating an index tree of at least one indexed object R; establishing a hash structure according to the ID (identifier) of the at least one indexed object R; and storing the lifetime of the indexed object (at each position of the index tree) in the hash structure. The technical scheme provided by the invention is applicable to large-scale relation data management systems, and an effect of high-efficiency and high-accuracy data indexing is achieved.

Description

Data indexing method and device

technical field

The invention relates to the field of data management, in particular to a data indexing method and device.

Background technique

In recent decades, data management technology has developed rapidly and played a prominent role in national economic construction. The large-scale relational database management system (Relational Database Management System, RDBMS) represented by Oracle, DB2, SQL Server, etc. is an indispensable core part of many large-scale information management systems and customer relationship management software. At the same time, the semi-structured data management technology represented by Extensible Markup Language (XML) also occupies a place in data exchange and data management lacking strict structure. The above technologies all have very high requirements on the data quality and the accuracy of the data to be processed. When the quality of the original data is not high, it needs to go through the preprocessing process to improve the data quality. Taking the departmental personnel management system as an example, information such as employee personal data, salary and benefits, and daily assessment must be accurate. However, in fields such as economics, military affairs, and telecommunications, data uncertainty is common, its existence is unknown, and there are errors in each attribute value. Although data preprocessing can improve the quality of the original data set, it may also lose some of the properties of the original data set, resulting in the inability to return high-quality query results. A typical application background is as follows.

Location-based service (Location Base Service, LBS) is the core issue in the field of mobile computing. Location service tracks moving objects (or users), and then locates the location of objects (or users) on the electronic map, and provides spatial information services based on this. In such applications, the position of the moving object is restricted by specific technical means (such as GPS (Global Positioning System, Global Positioning System) technology), and there is a certain error. Although this error will gradually narrow with the improvement of technical means, the problem of "location privacy" is becoming more and more prominent. The location information of moving objects is very important, and some users are reluctant to disclose it to avoid trouble. The purpose of "location privacy" is to reduce the accuracy of location - at a certain moment, the moving object is not in a certain spatial "point", but in an "area", thereby protecting privacy. At the same time, each Internet service provider can still provide corresponding services according to this "area" information, for example, inquire about facilities such as hospitals and hotels near the mobile object.

Indexing technology is an important part of data management technology. Relational databases often use B+ trees and their variants to index one-dimensional data; in the field of multidimensional data management or time-spatial data management, R trees and their variants are widely used for indexing. These indexing technologies can greatly improve the query processing speed. Similarly, indexing issues also need to be paid attention to when dealing with uncertain data. In some query tasks, such as top-k query, the probability value of the tuple is also very important, so it is necessary to create a one-dimensional index for the probability dimension, and the traditional index technology is effective at this time. But traditional indexing techniques cannot solve all problems.

When the value of each tuple must be described by a probability distribution function, and the probability distribution function cannot be specified in advance, the indexing efficiency of the traditional indexing technology will be greatly reduced and cannot meet the application requirements.

Contents of the invention

The invention provides a data indexing method and device, which solves the problem that the traditional indexing technology cannot meet the needs of large-scale data retrieval.

A data indexing method, comprising:

creating an index tree of the at least one indexed object R;

Build a hash structure based on the ID of at least one indexed object;

The lifetime of each position of the indexed object in the index tree is stored in the hash structure.

Preferably, said creating an index tree of at least one indexed object R includes:

Create the top-level TPR-Tree;

There is at least one 2-dimensional R-Tree linked under the TPR-Tree;

Link each R-Tree to a one-dimensional R-Tree through a hash link.

Preferably, the lifetime of each position of the indexed object stored in the hash structure in the index tree is specifically:

The lifetime of the indexed object in the TPR-Tree or the 2-dimensional R-Tree or the 1-dimensional R-Tree is stored in the hash structure.

Preferably, the above data indexing method also includes:

When performing a time interval query or a time slice query on any indexed object, look up the lifetime of the indexed object through the hash structure;

According to the lifetime corresponding to each position of the indexed object in the index tree, the position of the index corresponding to the indexed object in the index tree is determined.

Preferably, the lifetime is specifically a time interval during which the indexed object is in the same state.

The present invention also provides a data indexing device, including:

An index tree creation module, configured to create an index tree of the at least one indexed object R;

A hash structure generating module, configured to establish a hash structure according to the ID of at least one indexed object;

An associating module, configured to store the lifetime of each position of the indexed object in the index tree in the hash structure.

Preferably, the index tree creation module includes:

The first creation unit is used to create the uppermost TPR-Tree;

The second creation unit is used to link at least one 2-dimensional R-Tree under the TPR-Tree;

The third creation unit links each R-Tree to a one-dimensional R-Tree through a hash link.

Preferably, the above-mentioned data indexing device further includes:

The indexing module is used to find the life cycle of the indexed object through the hash structure when performing time interval query or time slice query on any indexed object, and according to the indexed object in the index tree The lifetime corresponding to each position in the index tree is used to determine the position of the index corresponding to the indexed object in the index tree.

The present invention provides a data indexing method and device. A hash structure is established according to the ID of at least one indexed object, an index tree of the at least one indexed object R is created, and the indexed object R is stored in the hash structure. The life cycle of each position of the index object in the index tree, the hash index and the index tree index are combined to index the data, which improves the index efficiency and index accuracy, and solves the problem that the traditional index technology cannot meet the requirements of large data retrieval. Questions needed.

Description of drawings

FIG. 1 is a flowchart of a data indexing method provided by Embodiment 1 of the present invention;

FIG. 2 is a schematic diagram of an index tree structure involved in an embodiment of the present invention;

FIG. 3 is a schematic diagram of the relationship between the hash structure and the index tree in an embodiment of the present invention;

FIG. 4 is a schematic structural diagram of a data indexing device provided by Embodiment 3 of the present invention.

Detailed ways

Indexing technology is an important part of data management technology. Relational databases often use B+ trees and their variants to index one-dimensional data; in the field of multidimensional data management or time-spatial data management, R trees and their variants are widely used for indexing. These indexing technologies can greatly improve the query processing speed. Similarly, indexing issues also need to be paid attention to when dealing with uncertain data. In some query tasks, such as top-k query, the probability value of the tuple is also very important, so it is necessary to create a one-dimensional index for the probability dimension, and the traditional index technology is effective at this time. But traditional indexing techniques cannot solve all problems.

When the value of each tuple must be described by a probability distribution function, and the probability distribution function cannot be specified in advance, the indexing efficiency of the traditional indexing technology will be greatly reduced and cannot meet the application requirements.

In order to solve the above problems, embodiments of the present invention provide a data indexing method and device. Embodiments of the present invention will be described in detail below in conjunction with the accompanying drawings. It should be noted that, in the case of no conflict, the embodiments in the present application and the features in the embodiments can be combined arbitrarily with each other.

First, Embodiment 1 of the present invention will be described with reference to the accompanying drawings.

An embodiment of the present invention provides a data indexing method, which can perform uncertain data management indexing. Traditional solutions generally use tree index or hash (Hash) index, but both tree index technology and hash index technology have their advantages and disadvantages. For example, tree index technology is suitable for random data access; hash index technology is suitable for sequential structured data, similar to broadcast channels. Tree index technology is very effective for data broadcasting of clusters; but clusters have little effect on the performance of hash index technology. Hash index technology is especially suitable for multi-attribute data index; tree index technology provides a more accurate and complete global view based on the index value, and the client can quickly find the arrival time of the desired data on the tree index, so that the coordination time Naturally shortened. Since the hash index does not contain the global information of the data frame, it can only help the client to determine whether the current data frame is related to the query. The effectiveness of its filtering depends largely on the average failure rate of the hash index.

The process of completing data indexing using the data indexing method provided by the embodiment of the present invention is shown in Figure 1, including:

Step 101, creating an index tree of the at least one indexed object R;

In the embodiment of the present invention, the top layer of the index tree is a TPR-Tree, and then multiple 2-dimensional R-Trees, and the hashes of the 2-dimensional R-Trees are linked to a 1-dimensional R-Tree. The index tree structure involved in the embodiment of the present invention is shown in FIG. 2 .

The TPR tree is a multi-way balanced tree with an R-tree structure. Each non-leaf node in the tree consists of several (TPBR, Point) units. TPBR is the bounding rectangle with time parameter that currently contains its corresponding child. Point is a pointer to the child node. The leaf node is composed of several (TPBR, ObjectlD). Among them, TPBR is a bounding rectangle with time parameter containing the corresponding moving object. ObjectID is a pointer pointing to the moving object, and the detailed information of the corresponding moving object can be obtained through the pointer.

R-tree is another form of B-tree's development to multi-dimensional space. It divides spatial objects into ranges. Each node corresponds to an area and a disk page. The disk pages of non-leaf nodes store all its children. The area range of a node, the areas of all sub-nodes of non-leaf nodes fall within its area range; the disk pages of leaf nodes store the circumscribed rectangles of all spatial objects within its area range. The number of sub-nodes that each node can have has upper and lower limits. The lower limit ensures the effective use of disk space, and the upper limit ensures that each node corresponds to a disk page. When inserting a new node, the space required by a node When larger than one disk page, the node is split in two (split). The R-tree is a dynamic index structure, that is, its query can be performed simultaneously with insertion or deletion, and the tree structure does not need to be reorganized periodically.

Step 102, establishing a hash structure according to the ID of at least one indexed object;

For all indexed objects, a hash structure (hash table) can be constructed according to their IDs.

Step 103, storing the lifetime of each position of the indexed object in the index tree in the hash structure;

In this step, the lifetime of each indexed object in TPR-Tree, R-Tree or (2-dimensional R-Tree+1-dimensional R-Tree) is stored in the hash structure.

The relationship between the hash structure and the index tree is shown in Figure 3.

Step 104, when performing time interval query or time slice query on any indexed object, look up the lifetime of the indexed object through the hash structure;

Step 105: Determine the position of the index corresponding to the indexed object in the index tree according to the lifetime corresponding to each position of the indexed object in the index tree;

In this step, when querying time intervals and time slices, the lifetime searched in the hash structure can be used to directly determine which index structure in the tree index to start searching.

Embodiment 2 of the present invention will be described below with reference to the accompanying drawings.

An embodiment of the present invention provides a data indexing method. The implementation process of applying the data indexing method provided in the embodiment of the present invention to a mobile communication environment will be described below. In the past ten years, with the development of wireless communication and positioning technology, location-based services (LBS) have been widely used. We assume that the communication company needs to track the real-time location of each mobile phone user in order to allocate reasonable bandwidth to a specific area to ensure smooth communication without congestion; or need to know the current location of the person who uses the mobile phone as a communication tool to call the police. All of this requires real-time tracking of the location information of mobile phone users. The mobile phone holder's movement may be complicated, but it is nothing more than static, similar to static, low-speed unlimited movement, and limited high-speed movement (this usually requires the use of transportation).

R-trees can be used to index mobile phone users' static and similar static states; TPR-trees can be used to index mobile phone users' low-speed unlimited movement; and (2-dimensional R-tree + 1-dimensional R-tree) can be used to index mobile phone users in Constrains stationary-like states in high-speed moving objects.

Each record in the composite index has a lifetime, and the so-called lifetime refers to the time interval during which the moving speed and direction of the object remain unchanged. It is represented by [t _start , t _end ].

For example, when a mobile phone user goes out to the train station, it is firstly indexed by the TPR-tree as a low-speed moving object; after the train starts, the original record is logically deleted ( _tend is equal to the current time), and a new special record is inserted into the TPR-tree , the record points to the corresponding high-speed moving object index. After reaching the destination, the special record is logically deleted, and an ordinary record is inserted into the TPR-tree.

For all objects to be indexed, a hash structure can be constructed according to their IDs, which also stores each object in a TPR-tree, R-tree or (2-dimensional R-tree + 1-dimensional R-tree) lifetime. For time interval query and time slice query, through the lifetime searched in the hash structure, you can directly determine which index structure to start searching from.

Embodiment 3 of the present invention will be described below with reference to the accompanying drawings.

An embodiment of the present invention provides a data indexing device, the structure of which is shown in Figure 4, including:

An index tree creation module 401, configured to create an index tree of the at least one indexed object R;

A hash structure generation module 402, configured to establish a hash structure according to the ID of at least one indexed object;

An associating module 403, configured to store the lifetime of each position of the indexed object in the index tree in the hash structure.

Preferably, the index tree creation module 401 includes:

The first creation unit is used to create the uppermost TPR-Tree;

The second creation unit is used to link at least one 2-dimensional R-Tree under the TPR-Tree;

The third creation unit links each R-Tree to a one-dimensional R-Tree through a hash link.

Preferably, the above-mentioned data indexing device further includes:

The indexing module 404 is configured to search for the life cycle of the indexed object through the hash structure when performing time interval query or time slice query on any indexed object, and according to the indexed object in the index The lifetime corresponding to each position in the tree determines the position of the index corresponding to the indexed object in the index tree.

An embodiment of the present invention provides a data indexing method and device, which establishes a hash structure based on the ID of at least one indexed object, creates an index tree of the at least one indexed object R, and then stores in the hash structure For the life period of each position of the indexed object in the index tree, the hash index and the index tree index are combined to index the data, which improves the indexing efficiency and indexing accuracy, and solves the problem that the traditional indexing technology cannot meet The problem of large data retrieval needs. Combining the two index technologies of tree index and hash index effectively improves the efficiency of multi-dimensional data management.

Those of ordinary skill in the art can understand that all or part of the steps of the above-mentioned embodiments can be implemented using a computer program flow, the computer program can be stored in a computer-readable storage medium, and the computer program can be run on a corresponding hardware platform (such as system, device, device, device, etc.), and when executed, includes one or a combination of the steps of the method embodiment.

Optionally, all or part of the steps in the above embodiments can also be implemented using integrated circuits, and these steps can be fabricated into individual integrated circuit modules, or multiple modules or steps among them can be fabricated into a single integrated circuit module accomplish. As such, the present invention is not limited to any specific combination of hardware and software.

The devices/functional modules/functional units in the above embodiments can be realized by general-purpose computing devices, and they can be concentrated on a single computing device, or distributed on a network composed of multiple computing devices.

When each device/functional module/functional unit in the above-mentioned embodiments is realized in the form of a software function module and sold or used as an independent product, it can be stored in a computer-readable storage medium. The computer-readable storage medium mentioned above may be a read-only memory, a magnetic disk or an optical disk, and the like.

Any person familiar with the technical field can easily think of changes or substitutions within the technical scope disclosed in the present invention, and all should be covered within the protection scope of the present invention. Therefore, the protection scope of the present invention should be based on the protection scope described in the claims.

Claims (6)

1. a data directory method, is characterized in that, comprising:

The index tree that creates at least one indexed object R, comprising: the TPR-Tree that creates the superiors; Under described TPR-Tree, chain is connected at least one 2 dimension R-Tree; Described 2 dimension R-Tree are connected to an one dimension R-Tree by hash chain chain link;

According to the ID of at least one indexed object, set up Hash structure;

In described Hash structure, store the lifetime of described indexed object each position in described index tree.

2. data directory method according to claim 1, is characterized in that, the described lifetime of storing described indexed object each position in described index tree in described Hash structure is specially:

In described Hash structure, store described indexed object and be in the lifetime in described TPR-Tree or described 2 dimension R-Tree or described one dimension R-Tree.

3. data directory method according to claim 2, is characterized in that, the method also comprises:

When arbitrary indexed object being carried out to time interval inquiry or timeslice inquiry, the lifetime of searching described indexed object by described Hash structure;

According to described indexed object lifetime corresponding to each position in described index tree, determine the position of described indexed object manipulative indexing in described index tree.

4. according to the data directory method described in claim 1 or 2 or 3, it is characterized in that, the described lifetime is specially indexed object lasting time interval under same state.

5. a data directory device, is characterized in that, comprising:

Index tree creation module, for creating the index tree of at least one indexed object R;

Hash structural generation module, for setting up Hash structure according to the ID of at least one indexed object;

Relating module, for storing the lifetime of described indexed object each position in described index tree in described Hash structure;

Described index tree creation module comprises:

The first creating unit, for creating the TPR-Tree of the superiors;

The second creating unit, is connected at least one 2 dimension R-Tree for chain under described TPR-Tree;

The 3rd creating unit, is connected to an one dimension R-Tree by the dimension of 2 in described the second creating unit R-Tree by hash chain chain link.

6. data directory device according to claim 5, is characterized in that, this device also comprises:

Index module, for when arbitrary indexed object being carried out to time interval inquiry or timeslice inquiry, the lifetime of searching described indexed object by described Hash structure, and according to described indexed object lifetime corresponding to each position in described index tree, determine the position of described indexed object manipulative indexing in described index tree.