Lucent Technologies Inc.

Sanjeev Khanna

Krishnan Kumaran

Francis Xavier Zane, Jr

Shanmugavelayut Muthukrishnan

Chandra S Chekuri

Vincenzo Liberatore

Shiyu Zhou

Techniques for watermarking structured data, such as map data are addressed. These techniques advantageously allow the detection of an unauthorized copy of the original data and to track the source of the unauthorized copy based upon a variety of opportunities to access the unauthorized copy. For example, in an Internet context, an unauthorized copy of a map may be provided to online customers so that they can make queries such as the distance between two driving destinations. Having such access, copies can be detected and traced to the original purchaser of the map.

Methods and apparatus for watermarking maps and other structured data

In accordance with the principles of the invention, a method and system of multiprocessor scheduling for load sharing among multiple multiprocessors to within any given error criteria, &egr;>0, is disclosed. The method comprises guessing a value for an optimal load on the processors, partitioning a plurality of multi-dimensional tasks into a set of large tasks and a set of small tasks, guessing the invention of the set of small tasks and among the set of larger tasks processors which are represented as multi-dimensional bins, packing a discretized the set of large tasks, in the guessed invention space of the multi-dimensional bins determining if the small tasks can be allocated into unallocated space of the multi-dimensional bins after packing of the discretized large tasks, and iteratively repeating the guessing steps until all the tasks can be allocated within the gussed load. The method establishes a schedule of the multi-dimensional tasks which provides a maximum load among the multi-processors which is less than (1&plus;&egr;) times the optimal load.

Method and system for load scheduling multidimensional tasks among multiple processors

A paging method for information retrieval from broadcast disk systems is described. In response to a page request (e.g., a request for an item of data), the method selectively stores and evicts, in and from a fast memory, pages of data broadcasted by the broadcast disk system. The methods proceeds using a three-&ldquo;color&rdquo; labelling scheme, wherein the label assigned to a broadcasted page is based on how recently a given page was last requested. If a requested page is stored in fast memory, then the request is immediately served. If the requested page is not stored in fast memory, the request cannot be served until the requested page is broadcasted. While waiting for the requested page to be broadcasted, certain &ldquo;somewhat-recently&rdquo; requested pages are &ldquo;prefetched,&rdquo; wherein they are stored in fast memory even though there is no pending request for such pages. Since the size of the fast memory is very small compared to the amount of information being broadcasted, only a small amount of the available information can be stored and there will be significant turnover in the particular stored pages as a function of the page requests. Pages are selected for eviction based upon the &ldquo;cost&rdquo; (to the competitive performance of the method) to replace the evicted page, wherein the least costly page to replace is evicted. The present method achieves a bounded competitive ratio of O (n log k), where n is the number of pages being broadcasted and k is the size of the fast memory.

Method for information retrieval in broadcast disk systems

A method and apparatus for determining an approximated solution to the partitioning of a two or greater dimensional array in an amount of time on the order of O(1). Given a desired maximum weight or a maximum number of partitions, an array of data is partitioned by determining a temporary division of the array of blocks such that each block has a weight of at least two times the desired maximum weight. Within each block, rectangles are determined which contain array elements greater than or equal to an arbitrary value corresponding to a guess at a maximum weight. From among these rectangles, a largest set of independent rectangles is determined, and partitions are defined based on the sides of the largest set of independent rectangles determined for each block. Select ones of the partitions may be deleted until a total number of defined partitions is equal to or less than a desired maximum number of partitions.

Apparatus and method for efficiently partitioning a weighted array

In some embodiments, the present invention provides a method for scheduling an indexed data broadcast such that both mean access time and mean tuning time are reduced to a practical minimum. In one embodiment of such a method, data items are first scheduled for broadcast. Such data items are advantageously scheduled such that: (1) all data items to be broadcasted are equally spaced; and (2) when indexed with appropriate &ldquo;indexing keys,&rdquo; the indexing information can be efficiently stored and broadcasted. In one embodiment, a schedule having a mean access time about 1.5&times; that of the theoretical minimum is provided. The indexing information is advantageously arranged in a way that allows for efficient delivery thereof to clients to apprise them of the broadcast schedule of the data items. The indexing information is advantageously arranged in a tree structure referred to herein as an &ldquo;indexing tree.&rdquo; Indexing information is advantageously stored at internal nodes of the indexing tree and data items are stored at the leaf nodes of the tree. The leaf nodes comprising the scheduled data items fall within &ldquo;subtrees&rdquo; of the various internal nodes of the indexing tree. Information indicative of the index keys of data falling within a subtree of a given internal node is stored at that node. According to a schedule, indexing information of the internal node is broadcasted, so that a client who is &ldquo;tuned in&rdquo; to the broadcast is apprised of the data that will be broadcasted as a subtree of the node. If desired data is not included in the subtree, it is safe for the client to stop listening to the broadcast (i.e., &ldquo;sleep&rdquo;) until such time as that portion of the broadcast is completed. By advantageously providing, in addition to the indexing information, the time at which the first internal node outside of the subtree will be broadcasted, the client can set an internal alarm and sleep until the set time.

Method and apparatus for indexed data broadcast

A method for operating a wireless telecommunications system whereby communication channels are efficiently allocated to cells of the system is provided. In accordance with an illustrative embodiment of the present method, call demand information is obtained for each cell in the wireless system and converted to a channel demand. Once the channel demand for each cell is known, a tentative channel allocation is performed. Call demand information can be obtained as frequently as desired to update channel allocation throughout the wireless system. In some embodiments, the method for channel allocation described herein can be used alone to allocate channels. In other embodiments, the present method for channel allocation can be used on an hourly, daily, or other temporal basis, as appropriate, to provide a channel allocation which is then updated on a substantially continuous basis by any conventional dynamic channel allocation scheme. To allocate channels, an 'interference graph' that relates interfering cells to one another is defined. When nearest-cell interference is considered, an initial step is performed wherein three channels are iteratively allocated to all cells in the system to remove all groupings within the interference graph comprising three mutually-interfering cells. During the initial step, the allocation of three channels reduces channel demand by one in every cell. Once the interference graph is free of such three-membered groupings, channel demand is reduced more efficiently wherein no more than five channels are allocated to satisfy two units of channel demand. To do so, a decomposition/reconstruction operation is performed wherein the interference graph is segregated into groupings of cells to which channels are allocated. The operation for allocating channels to cells when nearest- and next-to-nearest-cell interference is considered does not use the initial step of allocating three channels. It does, however, proceed in a manner analogous to the decomposition/reconstruction process mentioned above, although the operation is performed on a cell-by-cell basis, rather than with groupings of cells.

Method for operating a wireless telecommunications system

A method for designing a wireless telecommunications system having a plurality of cells is provided. In one embodiment of such a method, a call demand per cell is estimated, and a channel demand based thereon is determined on a cell-by-cell basis. The cell-by-cell channel demand is used to provide a reasonably tight upper bound on the number of communication channels required to satisfy the system-wide call demand. It is implicit in the procedure for estimating the upper bound that no mutually 'interfering' base stations use the same channel (i.e., frequency). 'Cliques' of mutually-interfering base stations or cells are defined. A channel demand is determined for each clique by adding up the channel demand for each cell in the clique. The greatest channel demand of all cliques determines a 'maximum clique demand' .omega..sup.d. The upper bound on the number of channels required to satisfy the system-wide call demand is given by the expression: .chi..sup.d .ltoreq.17/12.multidot..omega..sup.d when mutually-interfering cells are adjacent cells, and is given by the expression: .chi..sup.d .ltoreq.2.multidot..omega..sup.d -d.sub.min when mutually interfering cells are adjacent cells and next-to-adjacent cells, wherein d.sub.min is a minimum channel demand of all cells in the system. Having a reasonably-good estimate of the upper bound on the system-wide channel requirement, a wireless service provider may then seek to obtain or allot a commensurate amount of frequency spectrum to support its system.

Growing community of inventors

Philadelphia, PA, United States of America

Sanjeev Khanna