A method for freeing memory in a device with limited memory storing penstrokes

SWEDEN ds) PATENT WRITING (13) C2 (ii) 520 485

<img file="SE520485C2_D0001.tif" />

(19) SE ₍₅₁)

International class ⁷

G06K 9/06, 11/18, G06F 3/033

PATENT AND REGISTRATION (45) (41) (22) (24) (62) (86) (86) (83)

Patent issued 2003-07

Application widely available 2003-05 The patent application was filed 2001-11

Running day 2001-11

Tribal application number

International filing day

Filing date for European patent application Deposit of microorganism (21)

<td> 15</td><td></td><td>number Q103770-4</td>

<td> 14</td><td></td><td></td>

<td> 13</td><td colspan="2">Application received as:</td>

<td> 13</td><td>X</td><td>Swedish patent application</td>

<td></td><td></td><td>completed international patent application with number</td>

<td colspan="3">i | converted European patent application 1_1 with number</td>

(30) Priority information (73) (72) (74) (54) (56) (57)

PATENTHARE Anoto AB, Scheelevägen 19 C 223 70 Lund SE

INVENTOR Mattias Bryborn, Lund SE, Erik Sparre, Lomma SE OMBUD AWAPATENT AB

NAME Device and computer program product for freeing up memory space in a device with limited memory space

CALLED PUBLICATIONS: - - SUMMARY:

A method for freeing memory in a device with limited memory. A plurality of pen features are inserted into the device, each of which is associated with one of a plurality of pages. Pen draws are stored in electronic form in the memory. According to the method, memory is released by erasing all the pen features associated with a specific page. The specific side is determined based on a time at which a side-associated pen pull is recorded by the device.

A computer program product includes computer programs for performing the method. A device has a data processing unit and a memory as well as means for performing the method.

<img file="SE520485C2_D0002.tif" />

The numbers in brackets indicate international identification code, INID code. Letters in clamps indicate international document code.

520 485

SUMMARY

A method for freeing memory in a device with limited memory. A plurality of pen features are inserted into the device, each of which is associated with one of a plurality of pages. Pen draws are stored in electronic form in the memory. According to the method, memory is released by erasing all the pen features associated with a specific page. The specific side is determined based on a time at which a side-associated pen pull is recorded by the device.

A computer program product includes computer programs for performing the method. A device has a data processing unit and a memory as well as means for performing the method.

520 485

Technical area

The present invention relates to a method, a device and a computer program product for freeing up memory space in a device with limited memory space, in which device a plurality of pens are recorded and stored in electronic form.

Technical background

A user device, for example one described in WO 01/26033, which is hereby incorporated by reference, may be substantially shaped as a pen. This pen-like device may have a built-in camera for reading a position coding pattern as well as data processing means for interpreting, storing and transmitting information from the position coding pattern. Furthermore, it may have a working memory for temporary storage of data recorded by the device and a storage memory for permanent or less temporary storage of data. Such storage memory may consist of, for example, one or a plurality of flash memories or other memories of suitable size and type.

The position coding pattern, for example one described in WO 01/26033, encodes coordinates of points on an imaginary surface which can be very large. Other examples of position coding patterns are described, for example, in WO 00/73983 and WO 01/26032, which are hereby incorporated by reference.

520 485

The position coding pattern can be applied to a substrate, for example a paper, in the form of, for example, printed, machine-readable markings. By reading the position coding pattern, the user unit can be brought to initiate predetermined functions or input information such as text or graphics based on the read coordinates. Advantageously, the position coding pattern can be divided into subareas for, for example, specific applications, but it can also be divided into subareas intended to correspond to a physical page size in, for example, a notepad. Such subdivisions can be interpreted by the user device as pages, so that the user device can process information entered from, for example, a page in a notepad as contiguous.

Permanent storage of data can be accomplished by transferring or synchronizing the contents of the user device's storage memory to, for example, a server, the user's computer or a personal digital assistant (PDA). Such synchronization can take place via suitable known communication medium such as, for example, short-range radio link (e.g. Bluetooth®), IrDA, cable, Internet, mobile phone or other technologies that allow electronic transmission of information.

As the user device is passed over a substrate with position coding pattern, the device registers and decodes the position coding pattern and calculates coordinate pairs for positions on a page corresponding to the substrate. Coordinate pairs, or series of coordinate pairs, can be stored in the user device and, if necessary, processed with, for example, character recognition for converting handwritten information into machine-readable information.

520 485

Detection of a series of coordinate pairs can be initiated by a pressure sensor in the user device detecting that it is deposited on a support.

The registration is terminated by the pressure sensor detecting that the user device is lifted from the ground. The series of coordinates generated between the user device being lowered and lifted is hereafter referred to as a pen stroke.

A pen draw can be stored in electronic form in the storage device of the user device along with, for example, information on what part of the position coding pattern, and / or at what time the pen move was recorded. For example, the start time of each pen draw can be recorded. With a coordinate resolution of the order of three coordinate pairs or more per millimeter, it will be appreciated that the amount of coordinate pairs recorded by the user device when, for example, a text is written down can become very large, especially if a high sampling rate, for example 50100 Hz, is used. However, the amount of coordinate pairs can be reduced by various forms of compression.

WO 99/50787 shows another concept in which reading of a position coding pattern is used to generate information about both the extension of a pen and the side of the pen.

Since the built-in storage memory capacity of the user device may be limited by the space available for embedding memory media in the user device, there is a risk that the user device's storage memory may become full.

One way of handling this is disclosed in US 6,055,552, where the pen pages of entire pages are deleted as the pages are sent from the device to a device such as a computer.

520 485

This means that it is necessary to refuel the memory contents to the computer at regular intervals so that the memory does not become full, which in turn limits the time during which the device can operate independently, ie without contact with the computer.

There is a need for a memory management procedure with no user interface, or with at least the simplest possible user interface.

Summary of the Invention

Thus, it is an object of the present invention to provide a memory management method having easy-to-understand user interface.

This object is achieved in whole or in part by a method according to claim 1, a computer program product according to claim 18 and a device according to claim 19. Preferred embodiments are shown in the dependent claims and in the attached description.

Thus, there is provided a method for freeing memory in a limited memory device into which a plurality of pen features are inserted. The pen features are each associated with each of several pages and stored in electronic form in the memory. When space in the memory is to be freed, all pencils associated with a specific page are deleted. The specific side is determined based on a time at which a side-associated pen pull is recorded by the device.

By releasing memory sideways instead of erasing individual pen moves, better organized memory management is achieved since only entire pages are deleted from the storage memory, whereby the number of detached pen moves remaining in the device memory and take up space will be reduced or completely eliminated, while memory

520 485 is released in well-defined and intuitive devices for the user. In addition, good correspondence is obtained between information on the substrate, ie the paper, and information in electronic form on the page. In addition, repeated transmissions of memory content to, for example, various servers, computers or PDAs are possible. Furthermore, by selecting the pages to be deleted based on the timing of the associated pen feature registration, the user's involvement in the memory release process can be completely or partially eliminated.

According to the method, the specific page can be determined based on the fact that its most recently registered pen features are registered earlier than any of the other pages' last registered pen features.

This is a way of selecting the pages whose pen features are to be removed, so that the pages used last are retained, while the older pages' pen features are removed, leaving room for new pen features. By deciding which pages to delete in this way, a rule that is easy to understand for the user is created: pages that have not been used for a long time are removed from memory.

Alternatively, the specific page may be determined by registering a pen feature associated with the specific page prior to a predetermined time. The predetermined date may be a specific date, or be related to the date the page was registered or used, such as, for example, a discount coupon being deleted two weeks after it was used. Alternatively, the predetermined time can be related to the current date, ie, for example, pages that are more than two weeks old are deleted.

This is another way of selecting the pages to be deleted, by which the oldest pages are selected,

520 485 whether used recently or not. This method can be particularly advantageous when using, for example, time-limited offers.

According to the method, the specific page can be determined by confirming one user's suggested page. While this procedure requires some user involvement, it may still be preferable in some situations, especially if there are pages that the user may want to keep, regardless of their age.

The invention may advantageously be practiced in the form of a computer program product or device comprising application-specific circuits such as ASIC. Thus, a computer program product comprising a computer program for freeing memory in a device with limited memory is encompassed.

Upon execution, the computer program performs the procedure described above.

The invention further comprises an apparatus for electronically recording pen features each associated with a page. Such a device may comprise a data processing unit having a memory with limited space for storing the pen features in electronic form. The data processing unit is arranged to free up space in the memory by erasing all the pen features associated with a specific page from the memory. The data processing unit is further arranged to determine the specific page based on a time at which a page-associated pen feature is registered by the device.

The invention is well suited for dealing with a situation where a plurality of pen features are recorded from a plurality of different pages which need not be used in any particular sequence and which can be used repeatedly even if other pages are used in between.

520 485

Brief description of the drawings

The invention will be described in more detail below with reference to the accompanying schematic drawings which, by way of example, illustrate presently preferred embodiments of the invention according to its various aspects.

Figure 1 shows schematically a prior art user device in which the present invention can be practiced.

Fig. 2 schematically shows a prior art coordinate system, which is divided into sides and sub-areas.

Fig. 3 shows a schematic sketch of a storage memory block, which can be included in the user device of Fig. 1.

Fig. 4 schematically shows a plurality of position coding patterned pages on which a plurality of pen features are applied.

Fig. 5 shows a Gantt diagram-like sketch of the distribution of the pen features in Fig. 4 over the sides and time.

Fig. 6 is a schematic sketch of the pen features of Figs. 4 and 5 stored in a memory block as in Fig. 3.

Fig. 7 schematically shows a page address range.

Fig. 8 shows a flow chart for a method for releasing memory in the device of Fig. 1.

Fig. 9 is a schematic representation of the data processing unit of the device according to Fig. 1.

Description of preferred embodiments

Fig. 1 shows a prior art user device 1, which is further described in, for example, WO 01/26033, WO 00/73983 and WO 01/26032. The device 1 has a camera 2 arranged to read in real-time a position coding pattern arranged on a support. Based

520 485: ···. ··; v on the position coding pattern, coordinates are calculated for the positions marked by the device tip 3. This tip may, but need not, be arranged to function as a standard pen tip for writing characters or images on a substrate such as a paper.

The device further has a data processing unit 7 comprising data capture means 6 intended to process incoming data from the camera 2, working memory 4 and storage memory 5, and a programmable data processor 10 in the form of, for example, a processor. In addition, the device may have a power supply unit 8 in the form of, for example, a battery and a communication unit 9 for communication with external units. Such communication devices can, for example, utilize IR technology, cable or short-range radio link such as Bluetooth®.

Figure 2 shows schematically a coordinate system 20 for an imaginary surface. Coordinates on the imaginary surface can be encoded by a position coding pattern, which can be applied to substrates. The coordinate system can be divided into a plurality of pages 21, 22, 23, 24, which can be subdivided into subgroups or subregions 25 of the imaginary surface. Position coding patterns that encode the coordinates covered by the respective page can be applied to a substrate, such as a paper, to enable an electronic copy of information recorded with the user device 1 on the substrate to be obtained. By page, here is meant a digital page, which may constitute, in whole or in part, an electronic copy of a physical substrate.

Thus, in a coordinate pair, it is possible to encode a unique page address to the page to which the coordinate pair belongs. The page address can then be decoded by the user device in connection with the registration, or later.

520 485

A pen feature can be stored in the device memory as a series of coordinate pairs, which describe the device's movement over a support provided with the position coding pattern. The pen draw may contain a page address indicating on which page or sub-area of ​​the imaginary surface the pen draw was recorded and a time point indicating when the pen draw was recorded.

In a method, as shown in Figure 8, for determining which pages (and associated pen features) to be erased from storage memory 5, it is convenient to determine in a first step 80 a time point for the last recorded (youngest) pen feature on each page. . Then, in a second step 81, the pages are selected for deletion, which has the oldest last registered pen feature.

In one embodiment, the determination of which pages to delete may be carried out in its entirety at the time when it is necessary to free up storage memory space.

Below, the procedure will be described in principle terms and then in the form of an example, in which eleven pen features are recorded on four different pages. The procedure of this example may seem trivial, but it should be borne in mind that the process is, in fact, intended and suitable for handling tens of thousands of pages and pens or more.

When identifying each page's most recently entered pen features, all the pen features stored in memory can be searched, whereby the page address and registration time are extracted for each of the pen features. Subsequently, records containing a time point for each page address are stored in a first sortable data structure in memory, which is hereinafter referred to as page address table since the data search key of the structure is the page address. The records are stored in the page address table so that a list of the page addresses that occur in the memory and the respective (youngest) time associated with each page address is obtained.

Optionally, the entries in the page address table may contain additional parameters, such as a measure of the memory space that can be freed by deleting pencils belonging to the page. The size A of the table can be selected based on the estimated number of page addresses in the device storage memory, the available storage memory, and the device processor speed.

However, in a device that holds pen features from a very large number of different pages, the data structure in which page addresses and times are stored can be very large.

In order to keep down the size of these data structures, a second sortable data structure is formed, hereinafter referred to as the time table, since the data structure's search key is the time. This second data structure also includes entries with page addresses and times for each page address's last registered pen features. While the first data structure is sorted by page address, the second data structure is sorted by record time. In this example, the time table is assumed to contain B records. Size B is selected based on factors such as the number of pages that need to be removed under normal conditions to release the desired amount of storage memory and the processor speed of the device.

In one embodiment, both the page address table and the time table can be so-called max-heaps. The advantage of these is that they take up relatively little storage space and that operations such as insertion and extraction of data values ​​become very fast, even when the heap is very large. One more

520 485 full description of heaps can be found in Kingston, JH: Algorithms &amp; Data Structures: Design, Correctness, Analysis, Addison-Wesley Publishing Co., 1995.

To determine which page URLs to search for, one can select a parent search interval, i.e., the range of page addresses to be searched in the device's storage memory and whose maximum registration times should be identified. The parent search interval can be selected at the beginning of the process as either the total number of available page addresses according to the page division of the imaginary surface or based on the total page address range stored in the device's memory. In the latter alternative, information regarding the highest and lowest page addresses stored in the device's storage memory can be used. Such information can be kept relatively easily accessible in the device.

The search is conveniently started at the lower limit of the parent search interval, whereby search in memory is made for page addresses belonging to a first sub-interval of the parent search interval, and the first data structure is filled as new page addresses are found in the interval. If the first data structure becomes full, the encountered page addresses already stored in the table will be updated with respect to the time. Other found page URLs will be compared with the largest page address of the data structure and replace it if the found page address is smaller than the largest page address. The page addresses that are larger than the largest page address will thus be crawled at a subsequent iteration. Thus, if the first data structure holds A records, the scan will occur

520 485 of the first sub-interval to result in the A lowest page addresses present in the device memory.

When the entire first search interval is scanned, records will be copied to the second data structure, which is sorted by time. If the second data structure holds a fewer number of records than the first data structure, the records that have the oldest dates will be transferred.

When the first data structure is scanned and records transferred to the second data structure, the first data structure is reset.

Subsequently, a second sub-interval is formed of page addresses, whose lower page address will be adjacent to the upper bound of the first sub-interval, and whose upper bound may coincide with the upper bound of the parent search interval.

Then, the device memory is searched again for the page addresses that are included in the second sub-interval, the first data structure will contain the A following sequential page addresses in the order of magnitude.

After searching the second sub-range's page addresses, the transfer of time points to the second data structure is repeated so that it will contain the entries corresponding to the pages which have the B oldest registration times among the 2A lowest page addresses.

Thereafter, the procedure of resetting the first data structure, creating a new sub-interval, searching page addresses in memory and transferring records to the second data structure are repeated until all or sufficient number of the page addresses present in the device memory are searched and

520 The 485 time table contains the B minimum max times, ie the B pages that have the oldest latest registration times.

If a binary heap is used as the other data structure, it may happen that the recording times included in the heap are not all correctly sorted.

However, the record is always obtained which in the other data structure has the maximum (ie the youngest) registration time.

To create a list of a number of pages to be erased from the device's storage memory, it is possible to create a third data structure which is a result table with C records, which table is filled by extracting C maximum values ​​from the time table. The result table is preferably arranged so that its extreme value is the page address whose last registered pen feature is at the back of time. In addition, it can advantageously be completely sorted, so that a priority list of the pages to be removed is obtained.

The second and third data structures can, but need not be the same size. The third data structure is arranged to contain the page addresses that have the oldest last registered pen features.

As an alternative, a sorted list can be used for the other data structure, which list can easily be re-sorted and thus indicate the pages to be deleted. Thus, no result table in the form of a third data structure is needed.

WO 01/75781, which is incorporated herein by reference, describes how pages may be associated with each other. One way to handle this in connection with memory release is to treat associated pages that

520 485 OOO HL- :. ::.

a unit, that is, if a page with which other pages are associated is deleted, the associated pages are also deleted from the device memory.

In order to further illustrate the method, reference is now made to Figures 4-7 how a number of pen features ak, at the times t_A-t_k, has been registered on four different pages 21-24, which may consist of four different position coding patterns provided. Pages 21-24 have page addresses PA1.-PA4, which can be read from the position coding pattern. For the times t_A-t_k applies to t _A &lt;tb &lt;t _c &lt;ta &lt;t _e &lt;tf &lt;t _g &lt;th &lt;ti &lt;tj &lt;t _k, that is, a is the first registered pencil draw and k is the last registered pencil draw.

In Fig. 4, a, b and h have been registered on a first page 21 at times t_A, t_b and t_hrs. On a second page 22, pen features c, d and k have been recorded at times t_c, t_d and t_k. On a third page 23, pen features e, f and j have been recorded at times t_e, t_f and tj and on a fourth page 24, pen features g and i have been registered at times t_g respectively ten.

Fig. 5 shows a Gantt schematic diagram with page addresses (PAi-PA₄) on the y axis and recording times t_A-t_k on the x-axis.

Fig. 6 shows a schematic sketch of how the pen-drawn ac can be stored in a storage memory in the device. In the sketch of Fig. 6, all pen features are stored in a sequence, but the invention is also applicable to pen features that are not stored in a sequence, but which are arbitrarily distributed in the storage memory of the device.

Figure 7 illustrates the search interval from PA_min_n (PA = Page Address) to PA_max. . PA_min_n may be 0 or the lowest page address stored in the device's storage memory, because PA_max can be the maximum possible page address according to

520 485 the position coding pattern or the highest page address stored in the device's storage memory. In the search interval, there are the page addresses of the four pages, ΡΑχ, PA₂, PA₃as well as PA₄.

Fig. 8 shows a flow chart of a method according to an embodiment of the invention.

In a first step (not shown), a first page address table 61. A table size is chosen to illustrate the principle, A = 3, ie the table will hold three page addresses. Furthermore, a timetable is formed. The size B of the time table is also set to 3, but it will be realized that other values ​​on the tables are also possible. A practical value of A and B, respectively, can be 100, but A and B must not be equal. A first search interval Ιχ is formed in step 70 and set to PA_min_n. . PA_max, where PA_min_n may be, for example, 0 or a known value for the lowest page address stored in the storage memory. Then, in step 70 ', a search is stored in the storage memory 5 for page addresses belonging to the search interval Ιχ. When a page within the search interval is first encountered in storage memory 5, it is stored in step 71 as an entry in the page address table 61. If the page address was found earlier, and thus is part of an existing record stored in the page address table 61, instead, the record's entry time is updated in the page address table in step 72, so that the page address table 61 contains the most recent record time for each page address. If the page address table size is limited and the page address table is full, the highest page address in the table can be replaced with a found page address if the found page address is lower than the highest page address in the table, so the page address table will contain the A lowest page addresses.

520 485

After an initial search, the page address table may look like the following:

Table 1: Page address table after first search.

<td>Page address</td><td>registration Time</td>

<td>PA₃</td><td></td>

<td>PA₂</td><td>t_k</td>

<td>ΡΑ_τ</td><td>t_hrs</td>

Then, a second data structure is formed, hereinafter referred to as time table 62. In step 74, time table 62 is populated with values ​​from the page address table, so that the time table 62 will contain entries copied from the page address table, and sorted with respect to the record time.

Table 2: time table after first search.

<td>registration Time</td><td>Page address</td>

<td>t_k</td><td>PA₂</td>

<td>j</td><td>PA₃</td>

<td>t_hrs</td><td>Pai</td>

Since A = 3 became the size of the first search interval PA_my-PA₃. Then, in step 75, a check is made as to whether all page addresses are crawled. If not, in step 70 a second search interval such as I2 = PA3 + I. is formed. PA_max.

A second search session is then made, whereby a second page address table, Table 3 is formed. As an alternative, the first page address table can be reset to form the second page address table.

After the second search session, the second page address table becomes as follows:

Table 3: Page address table after second search.

520 485

<td>Page address</td><td>registration Time</td>

<td>PA₄</td><td>t</td>

<td></td><td></td>

<td></td><td></td>

Now all the page URLs have been found and thus no new search interval needs to be created. If, on the other hand, there were additional page addresses in memory, entries from the page address table would be transferred to the time table, then the page address table will be reset, a new search interval will be created, and a new search will be performed.

Since the time table is not reset, the last registration time ti for the fourth page is compared

PA4 with the latest registration date in the time table, t_k, whereby it is determined that ti &lt;t_k and thus ti shall replace t_k, so that the time table looks as follows:

Table 4: instantaneous picture of the time table after t replaced t_k.

<td>registration Time</td><td>Page address</td>

<td>t</td><td>PA₄</td>

<td>t</td><td>PA₃</td>

<td>t_hrs</td><td>Pai</td>

The time table is then sorted, giving the following appearance:

Table 5: the time table after t replaced t_k and table 20 is sorted.

<td>registration Time</td><td>Page address</td>

<td>t</td><td>PA₃</td>

<td>t</td><td>PA₄</td>

<td>t_hrs</td><td>Pai</td>

520 485

Now Table 5 points to the three pages that have the oldest latest registration times, but since the time table in the example is a max-heap, the times will be in the wrong order. This can be remedied by forming a third data structure 63, referred to below as the result table, Table 6. This table has a size C, which is set here to 3. The result table is gradually filled up from below in step 77 by repeatedly extracting the maximum value from the time table in step 76, so that the following appearance is obtained:

<td colspan="2">Table 6: Results table.</td>

<td>registration Time</td><td>Page address</td>

<td>t_hrs</td><td>ON!</td>

<td>t</td><td>PA₄</td>

<td>t</td><td>PA₃</td>

Table 6 now shows a table that correctly specifies the order in which pages should be deleted in step 78 from the device's storage memory 5. In connection with (i.e., before or after) deletion in step 78, in step 79 a check is made that the memory released by the method is sufficient according to the criteria established for the amount of memory to be released. If not enough memory is released, the procedure starts from step 70 at the beginning.

Suitable data structures for practicing the invention should be of such a type that they have at least the insert, find and remove functions. Examples of such data structures that can be used are symbol tables such as sorted lists, search trees (binary, B trees, Splay trees), stacks or hashtags. Priority queues such as heap-arranged trees or binary heaps can also be used. A number of such

520 485 data structures are described in Kingston, JH: Algorithms &amp; Data Structures: Design, Correctness, Analysis, AddisonWesley Publishing Co., 1995.

If a regular, fully sorted table is used instead, it can easily be rearranged so that the desired sequence is obtained. It may also be advantageous to cascade one or more symbol tables.

As another alternative to the aforementioned data structures, it is possible to use an unsorted vector in which linear search is performed.

Fig. 9 schematically shows a data processing unit 7 in a device 1 suitable for implementation of the above-described method. The data processing unit may contain a general-purpose programmable processor or signal processor, provided with appropriate software for performing the procedure, or a circuit specifically adapted for the purpose (ASIC type or similar). Further, the data processing unit may have a storage memory 5, in which, for example, pen features 30 can be stored and a working memory 4, in which data structures 61-63 can be stored, among other things.

Further, the device may have means 50 for identifying a plurality of page addresses stored in memory, and the time of the last registered pen draw associated with each page address, means 51 for selecting a page from the identified pages, which page's last registered pen features are the longest back in time. , and means 52 for deleting the selected page from memory 5.

Further, the means for identifying a plurality of pages may comprise means 53 for searching the memory for a plurality of pen-associated page addresses, means 54 for storing a page address found in the memory and associated time in a first data structure,

520 485 and means 55 for updating the time when a page address stored in the first data structure 61 is found in memory so that the last time of the page address is stored in the first data structure 61.

The page selection means 51 may further comprise means 57 for forming a second data structure 62, which is intended to receive and arrange page addresses and times from the first data structure 61 based on the time at which each page address's last registered pen features were registered, and means 56 for identification in the second data structure 62 of the page whose timing is at the back of the time.

The second data structure 62 can contain a predetermined number of records, which are sorted so that at least one extreme value, ie a maximum (max) or minimum (min) value, is obtained, corresponding to the page address associated with the last registered pen move.

The means 56 for identification may comprise means 58 for forming a third data structure 63, which may, but need not, contain as many page addresses as the second data structure 62, means 59 for extracting the extreme value from the second data structure 62, and means 60 for repeated filling from below or from the back of the third data structure 63 with the extreme value of the second data structure 62 until the third data structure 63 is full. The third data structure is advantageously made up of a table that is sorted so that the page address that has the smallest, ie oldest, time comes first and the page address that has the largest, ie last time comes last. The table is filled from the back by repeatedly extracting the maximum values ​​from the other data structure and entering from the bottom from the table.

520 485 r ο - 21

The above-described method is intended to be used in a situation where the device memory storage is limited and where there is no upper limit on how many pages may be present in the device storage memory. Therefore, the procedure is also performed at the times when the device's storage memory becomes full.

The process can be relatively easily implemented in real time if the device is provided with sufficient working memory or storage memory to be able to accommodate data structures of the size that would be required to scan a very large number of page addresses. In such a real-time process, page address tables and time tables can be updated as new pen features are recorded and pages are deleted from storage memory as they are filled.

As an alternative, in performing the method in real-time, it is possible to limit the number of page addresses that may be present in the device's storage memory so as to keep the page address table and time table sizes down.

Fig. 3 shows how pen features can be stored as sequences of data bits in a storage device 5 of a user device 1 and especially then in a flash-type storage memory. In Fig. 3, storage memory 5 is shown as a series of positions 31-39. The positions can be of variable length, ie including different number of data bits.

Figure 3 further shows schematically how pen features are sequentially stored. A pen draw 30, which will be described in more detail below, is stored after a previous pen draw 30 'and before a subsequent pen draw 30' '.

A pen pull 30, 30 ', 30' 'can be of variable length 30a, since it consists of two parts: one part of

520 485 fixed length 30b with data that applies to the entire pen draw and a portion of variable length 30c which includes, inter alia, the coordinate pairs XY included in the pen draw. The second part may also contain additional information related to the respective coordinate pairs, as described below.

The first portion 30b may have a stroke header SH indicating that a new pen pull follows in the storage memory as well as an offset OS that talks about the number of bits that exist between the beginning of this pen pull 30b and the beginning of the next pen pull 30 ''. Furthermore, the first part may have a time ST indicating when the pen draw was registered, for example start time or end time for the pen draw registration. Furthermore, the first portion 30b may include a page address PA which indicates on which side of the imaginary surface the pen feature 30 is registered or started to be registered. Thus, each electronically stored pen feature is associated with a page via a page address PA. The page address PA may have a plurality of fields, for example, representing the page's relation to the imaginary surface, such as belonging to subareas, type of territory, etc. The total amount of page addresses can be seen as a continuum of page addresses and is thus compared to numbers on a number line. Thus, based on the relationship of the page addresses, it can be said that a first page address is greater than a second page address if the first page address is to the right of the second page address on the number line.

The second portion 30c of the pen draw 30 may be of variable length since it may contain the entire series of coordinate pairs included in the pen draw. The series of coordinate pairs can be of varying length depending on the length of the pen draw. The series of coordinate pairs is stored in the order in which the coordinate pairs are recorded. Thus, it is possible to become aware of the user device

520 485 sampling rate and the start time of the pen draw, determine when each coordinate was registered. According to one embodiment, for each registered coordinate pair, a coordinate header CH may be stored which can specify a format in which the corresponding coordinate pairs are stored, i.e. whether the coordinates are compressed, whether they include order number CN for each coordinate pair, and whether they include force components or angular indications for the orientation of the user device at registration.

A pen draw may also include an EOS (end of stroke) indicating the end of the pen draw. This EOS can be provided with an indication that the pen move goes over several pages, that is, the pen move creates an association between the pages. In addition, the associated page address can be identified in EOS. It is also possible in the SH to provide an indication that the pen feature is included in an association and which page address is included in the association.

When a pen pull starts to register, ie the user device is lowered to a support, a stroke header SH is first written to the storage memory. This can initially be set to a value indicating that the pen move is incorrect. When the user device is then lifted from the ground and the pen draw is completed, stroke header SH can be rewritten to a value indicating that the pen draw is normal. In addition, the offset OS can be updated to indicate the correct length of the pen draw. In this way, interrupted pen moves in the storage memory can be registered as incorrect if an interruption should occur during the ongoing registration of a pen drive. These incorrect pen features can, for example, be recycled as far as possible or simply erased.

520 485

When a pen string 30 is to be deleted from the storage memory, this can be done by rewriting the stroke header SH to a value indicating that the space is deleted. Thus, the storage memory space on which the pen feature is stored becomes available for writing new information as soon as the storage memory space is defragmented.

Release of storage memory 5 can be initiated when a certain amount of storage memory 5 is full. Once the storage memory release is initiated, this can continue until a certain amount of storage memory is available. As an example, the storage memory release can be initiated when 3% of the storage memory is free and terminated when 10% of the storage memory becomes free. After releasing storage memory, it is convenient to defragment the storage memory in a manner known to those skilled in the art.

Furthermore, when releasing storage memory, it is advisable to lock the pages used, for example, the most recently registered pages so that the previously registered contents of them do not disappear when a storage memory is released while the user is in the process of entering new pen features on the page. .

An alternative way to choose which pages to delete is to let the user determine this. A first example of how this can be done is that each page is provided with a deletion field, whereby all associated pen features are deleted from the device's storage memory when this field is marked with the device.

A second example is that by means of a suitable method, for example according to a method as described above, the device selects a number of pages that can be deleted and proposes them to the user via a suitable interface (e.g. a PDA, mobile phone, computer etc.),

520 485, giving the user the opportunity to confirm which pages to delete from the storage memory.

A third example is that users type or otherwise enter a delete command and, in conjunction with this, appropriately designate a page to be deleted.

Another way to select pages that can be deleted from storage memory is to specify a date at which each page should be deleted. This can be done, for example, by creating an erase table in the device, listing pages with the best before date.

This can be particularly advantageous when registering pen features from, for example, pages linked to time-limited offers such as advertisements, etc. Possibly this can also be combined with an appropriate reminder mechanism.

An alternative to this is to delete all pages that have a pen feature older than a certain, predetermined date.

A further alternative is that as soon as all pencils associated with a page are sent to an external device, such as a computer, a PDA, a server, etc., those pages are deleted from the device's storage memory.

It is also possible within the scope of the present invention to combine the above-described methods.

For example, pages within the imaginary surface can be classified to give different properties prior to deletion or sorting. Thus, pages of some types can be readily erasable without the user's involvement, while pages of other types require the user to confirm that they may be deleted. Some page types may be specified to be removed automatically

520 485 after a certain date and others can be removed in conjunction with being sent to an external device.

Furthermore, it is possible to transfer information between the device's storage memory and working memory so that data, such as pen features, data structures and the like are accessible for processing from the memory which is found to be most suitable for the purpose. Thus, the working memory and the storage memory may be interchangeable with respect to where the process is performed and the data is stored.

520 485