Storage method and search method for mark event on two-dimensional space

• US 8,156,162 B2
• Filed: 07/30/2008
• Issued: 04/10/2012
• Est. Priority Date: 02/18/2008
• Status: Active Grant

• Current Assignee: Industrial Technology Research Institute
• Original Assignee: Industrial Technology Research Institute
• Inventors: Lee, Ching-Sung, Chang, Shih-Fang
• Primary Examiner(s): Coby, Frantz
• Application Number:
  US12/182,142
• Publication Number:
  US 20090210410A1
• Time in Patent Office: 1,350 Days
• Field of Search: 707/812, 707/758, 707/760, 707/743, 382/305, 345/568, 375/142, 706/45, 701/200
• US Class Current: 707/812
• CPC Class Codes: G06F 16/9537 Spatial or temporal dependent retrieval, e.g. spatiotemporal queries

Abstract

A storage method and a search method for mark events on two-dimensional space are provided. First, an event and a corresponding coordinate thereof are retrieved. Next, calculation on the coordinate of the event is performed to generate an index representing a bucket position in a storage device. Next, whether or not there is any existing search tree stored in the bucket position is judged, and then the event is inserted into a linked list of a node of the search tree stored in the bucket position according to a judgment result. Besides, when a range on the two-dimensional space is designated, corresponding nodes in the search tree are rapidly accessed according to the index obtained by a hash function, and further by application of pointers pointing to the bucket position having the search tree stored therein and by real-time return of search result, the search speed is high.

Claims

1. A storage method for mark events on a two-dimensional space, comprising:

providing one of the events and a first degree and a second degree of a coordinate of said one event;

performing calculation on the first degree according to an algorithm, to obtain an index pointing to a bucket position of a storage device;

judging whether or not there is a search tree stored in the bucket position;

inserting said one event into a linked list of a node, corresponding to the second degree, of the search tree, if any search tree stored in the bucket position, wherein the linked list is composed of a plurality of the events and does not include any node of the search tree, each node of the search tree is corresponding to a different second degree of the coordinates of the events; and

establishing a new search tree whose a root node being the second degree of said one event, and inserting said one event into the linked list of the root node of the established search tree, if there is no any search tree stored in the bucket position.

2. The storage method for mark events on a two-dimensional space as claimed in claim 1, wherein the first degree of said one event is in type of one of a longitude and a latitude, and the second degree of said one event is in the other type.

3. The storage method for mark events on a two-dimensional space as claimed in claim 2, wherein the first degree and the second degree of said one event are in numerical format or in degree-minute-second format.

4. The storage method for mark events on a two-dimensional space as claimed in claim 1, wherein the algorithm is a hash function.

5. The storage method for mark events on a two-dimensional space as claimed in claim 1, wherein the search tree is a balance tree or a height-balanced tree.

6. The storage method for mark events on a two-dimensional space as claimed in claim 1, wherein:

the bucket position further has a pointer pointing to a next non-empty bucket position or to a previous non-empty bucket position; and

when the search tree is newly established, a pointer of the previous non-empty bucket position or a pointer of the next non-empty bucket position is renewed.

7. A search method for mark events on a two-dimensional space, comprising:

designating an inquiry range on a map, wherein coordinates of the inquiry range relates to a first degree, a second degree, a third degree and a fourth degree;

performing calculation on the first degree and the third degree according to an algorithm to obtain a first index and a second index, wherein the first index and the second index respectively point to a first bucket position and a second bucket position of a storage device;

searching a search tree stored between the first bucket position and the second bucket position;

searching a corresponding node of the found search tree stored between the first bucket position and the second bucket position while taking the second degree and the fourth degree as searching conditions; and

returning back all the events stored in the matched nodes, and real-time displaying the events on the two-dimensional space.

8. The search method for mark events on a two-dimensional space as claimed in claim 7, wherein the first degree and the third degree are in type of one of a longitude and a latitude, and the second degree and the fourth degree are in the other type.

9. The search method for mark events on a two-dimensional space as claimed in claim 8, wherein the first degree, the second degree, the third degree and the fourth degree are in numerical format or in degree-minute-second format.

10. The search method for mark events on a two-dimensional space as claimed in claim 7, wherein the algorithm is a hash function.

11. The search method for mark events on a two-dimensional space as claimed in claim 7, wherein the search tree is a balance tree or a height-balanced tree.

12. The search method for mark events on a two-dimensional space as claimed in claim 7, wherein:

each of the bucket positions within the storage device has a pointer pointing to a next non-empty bucket position or to a previous non-empty bucket position; and

when the search tree is newly established, a pointer of the previous non-empty bucket position or a pointer of the next non-empty bucket position is renewed.