Data sorting method and navigation method and system using the sorting method
First Claim
Patent Images
1. A computer-implemented navigation method for displaying point of interest (POI) information for selecting a destination, comprising the following steps of:
- specifying a category of POI in a navigation system for displaying a list of specified POIs;
collecting a predetermined number (N) of POIs in an input data array;
defining a number A of POIs to be contained in each block to produce a series of blocks each having the sorted POIs, where X is smaller than N, and a total number of blocks is N/(X−
B);
sorting the POIs by distance from a predetermined position in a forward order or a reverse order to produce a block of POIs sorted by distance where each block has A of POIs;
displaying a list of POIs using the block of POIs sorted by distance and scrolling the list of POIs on a display screen in response to a scroll request; and
repeating the above steps of sorting the POIs and displaying the POIs to produce another block of sorted POIs when the sorted POIs from previous sorting become insufficient for a further scroll request.
1 Assignment
0 Petitions
Accused Products
Abstract
A computer-implemented data sorting method for sorting data at high speed with small memory capacity. The sorting method sorts an array of data where sorted data is constituted by a combination of a plurality of blocks where each block is produced separately from one another during the sorting process. In another aspect, a navigation method and system utilizes the data sorting method for quickly sorting and displaying requested information such as POIs sorted by distance with use of a small memory.
-
Citations
20 Claims
-
1. A computer-implemented navigation method for displaying point of interest (POI) information for selecting a destination, comprising the following steps of:
-
specifying a category of POI in a navigation system for displaying a list of specified POIs;
collecting a predetermined number (N) of POIs in an input data array;
defining a number A of POIs to be contained in each block to produce a series of blocks each having the sorted POIs, where X is smaller than N, and a total number of blocks is N/(X−
B);
sorting the POIs by distance from a predetermined position in a forward order or a reverse order to produce a block of POIs sorted by distance where each block has A of POIs;
displaying a list of POIs using the block of POIs sorted by distance and scrolling the list of POIs on a display screen in response to a scroll request; and
repeating the above steps of sorting the POIs and displaying the POIs to produce another block of sorted POIs when the sorted POIs from previous sorting become insufficient for a further scroll request. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
10. A computer-implemented data sorting method for sorting an array of input data in a specified order to a plurality of blocks, comprising the following steps of:
-
(a) defining a number of data entries A for each block when the input data array has N entries and a total number of blocks is N/(X−
B), where X is smaller than N;
(b) creating a buffer of X=A+B entries configured by a series of a sorted buffer of A entry positions and a working buffer of B entry positions;
(c) defining “
previous high” and
a reference entry where the previous high is a highest value in a block of sorted entries obtained in an immediately previous sorting and the reference entry is a value in a last entry position of the sorted buffer;
(d) searching an entry that satisfies conditions of (1) larger than the previous high and (2) smaller than the reference entry and loading the entry that satisfies the conditions in the sorted buffer;
(e) sorting the entries in the sorted buffer in a forward order when the sorted buffer is full;
(f) searching an entry that satisfies conditions of (1) larger than the previous high and (2) smaller than a new reference entry and loading the entry that satisfies the conditions in the working buffer;
(g) sorting the entries in the buffer in the forward order when the buffer is full;
(h) repeating the above steps (f)-(g) until no entry satisfies the conditions in the step (f); and
(i) producing a block of sorted entries by taking the entries A from the sorted buffer. - View Dependent Claims (11, 12, 13)
-
-
14. A computer-implemented data sorting method for sorting an array of input data in a specified order to a plurality of blocks, comprising the following steps of:
-
(a) defining a number of data entries A for each block when the input data array has N entries and a total number of blocks is 2N/(X−
B), where X is smaller than N;
(b) creating a buffer of X=A+B entries configured by a series of a sorted buffer of A entry positions and a working buffer of B entry positions;
(c) defining “
previous low” and
a reference entry where the previous low is a lowest value in a block of sorted entries obtained in an immediately previous sorting and the reference entry is a value in a last entry position of the sorted buffer;
(d) searching an entry that satisfies conditions of (1) smaller than the previous low and (2) larger than the reference entry and loading the entry that satisfies the conditions in the sorted buffer;
(e) sorting the entries in the sorted buffer in a reverse order when the sorted buffer is full;
(f) searching an entry that satisfies conditions of (1) smaller than the previous low and (2) larger than a new reference entry and loading the entry that satisfies the conditions in the working buffer;
(g) sorting the entries in the buffer in the reverse order when the buffer is full;
(h) repeating the above steps (f)-(g) until no entry satisfies the conditions in the step (f); and
(i) producing a block of sorted entries by taking the entries A from the sorted buffer. - View Dependent Claims (15, 16, 17)
-
-
18. A computer-implemented navigation system for displaying point of interest (POI) information for selecting a destination, comprising:
-
means for specifying a category of POI in a navigation system for displaying a list of specified POIs;
means for collecting a predetermined number (N) of POIs in an input data array;
means for defining a number A of POIs to be contained in each block to produce a series of blocks each having the sorted POIs, where X is smaller than N, and a total number of blocks is N/(X−
B);
means for sorting the POIs by distance from a predetermined position in a forward order or a reverse order to produce a block of POIs sorted by distance where each block has A of POIs;
means for displaying a list of POIs using the block of POIs sorted by distance and scrolling the list of POIs on a display screen in response to a scroll request; and
means for repeating the above procedure of sorting the POIs and displaying the POIs to produce another block of sorted POIs when the sorted POIs from previous sorting become insufficient for a further scroll request. - View Dependent Claims (19, 20)
-
Specification