Panasonic Technologies, Inc.

Matsushita Electric Industrial Co., Ltd.

Walid G Aref

Ibrahim Mostafa Kamel

Sarit Mukherjee

Daniel Barbara

Dennis Bushmitch

David Alan Braun

Stephen L Johnson

Junichi Kanai

Shahram Ghandeharizadeh

Rafael Alonso

Thirumale N Niranjan

Sharad Mehrotra

Padmavathi Vallabhaneni

Keyword proximity searching in a document database according to a query condition initiates with generation of inverted lists having a location for each instance of the keyword in the document database. A plane-sweep mode is used to efficiently search the inverted lists until an output tuple satisfying proximity criteria in the search query is detected. The method then shifts to a nested-loop search mode to enumerate all possible combinations of the keyword instances that satisfy the proximity search query which are in the neighborhood of the output tuple detected in plane-sweep mode. The method alternates between these two modes of operation until all of the output tuples satisfying the query condition are enumerated.

Method for keyword proximity searching in a document database

A method for searching for a query word in a database of automatically recognized text generated, for example by an optical character recognition (OCR) system or a speech recognition (SR) system finds entries that most closely match the query word. The database is indexed into a trie data structure, which represents all possible words in the database. The trie data structure has a plurality of branch nodes, each representing a letter of at least one word, and a plurality of leaf nodes, each representing a respective word. The trie data structure is searched for each query word by selecting the first letter of the query word and also selecting a root node in the trie data structure as the current node. All possible child nodes of the current node are identified. Respective estimated probability values for matching respective letters of the query word with the letters associated with the nodes in the path taken through the trie data structure are calculated for each identified child node. The identified child nodes are then placed into a list of candidate nodes. The node, in the list of candidate nodes, having the highest probability value is selected as the current node and is then deleted from the list of candidate nodes. The process repeats with this current node until a leaf node is reached. When a leaf node is reached, a determination is made whether to store the word into a list of best matches based on the probability value of the word compared to the probability values for all the words in the list of best matches.

Method for searching in large databases of automatically recognized text

A distributed file system using autonomous disks is disclosed. The file system includes autonomous data disks that store the application data of the distributed file system. Legacy attribute disks store the file system's meta-data and directory structure. The directory structure is stored on the legacy attribute disks using the native file system. One of the clients of the file systems is utilized as a configuration manager to control access to the system. The distributed file system employs agents to support real-time applications and concurrent read/write to files.

Real-time distributed file system

A computer-implemented scheduling method and apparatus for scheduling operations relating to a predetermined activity. The activity includes scheduling operations of network-attached storage devices, or other computer-related operations, or non-computer related operations, such as manufacturing plant operations. Operational data is received that is indicative of the operations. Attributes regarding the received operational data are identified. A linear ordering of the attributes is imposed via a predetermined curve. The curve is an aggregation of at least substantially continuous functions from intervals so as to form a substantially repetitive pattern. Operations are scheduled based upon the imposed linear ordering. With such an approach, the overall performance aspects of the system is significantly improved.

Scheduling method and apparatus for network-attached storage devices and other systems

A process is presented for supporting simultaneous disk read and write requests in a video server environment. Read requests are the result of movie viewing, while write requests are the result of video clip editing or movie authoring procedures. Due to real-time demands of movie viewing, read requests have to be fulfilled within certain deadlines, otherwise they are considered lost. Since the data to be written into disk is stored in main memory buffers, write requests can be postponed until critical read requests are processed. However, write requests still have to be proceeded within reasonable delays and without the possibility of indefinite postponement. This is due to the physical constraint of the limited size of the main memory write buffers. The new process schedules both read and write requests appropriately, to minimize the amount of disk reads that do not meet their presentation deadlines, and to avoid indefinite postponement and large buffer sizes in the case of disk writes.

Video server scheduling for simultaneous read-write requests

Multi-media servers provide clients with streaming data requiring soft real-time guarantee and static data requiring a large amount of storage space. The servers use a pull-mode protocol to communicate with clients through a real-time network. Separate data and control channels enhance the soft real-time capability of the server. The data channel conforms to open standard protocol. A switched data link layer for the control channel permits separate intrahost control messages that may be multicast and broadcast. The distributed file system selects a specific data block size based upon the compression technique employed to enhance soft real-time guarantee. A hierarchal data structure combined with merging empty data blocks minimizes disk fragmentation. Data blocks are striped across multiple disks to improve disk utilization. A local buffer and a queue for both read and write requests provides support for simultaneous read and write data streams.

Inexpensive, scalable and open-architecture media server

A transport system allows delivery of MPEG video streams from a network server to a media client while avoiding network delays associated with transition between files contained in these streams. A buffering system, a transport controller, and a counter allow buffering and interim delivery of MPEG stream data. The transport controller can either deliver MPEG stream data directly to the media client, or route data through the buffering system. The buffering system includes a population buffer for storage of interim MPEG stream data, and a transport buffer for temporary storage of MPEG stream data during continuous delivery. During transitional delivery, the transport controller delivers interim data to the media client until the requested file is available and uses the counter to select the proper start location in the requested file.

Algorithm for fast forward and fast rewind of MPEG streams

The distributed multimedia server employs modular server elements that connect with client systems through a high bandwidth network. The server elements are connected in interleaved fashion with the switching elements and the data representing different media selections are arranged in stripe groups distributed across the server elements. The server can be as small as a single server element or grown incrementally, as needed, by connecting additional server elements to the system. Multiple copies of hot media selections are stored across the distributed architecture within different stripe groups to minimize bottlenecks within the storage subsystem.

Seamless scalable distributed media server

The disk scheduling system supports the processing of simultaneous storage device read and write requests in a video server environment, thereby supporting both video-on-demand and non-linear editing applications. Read requests are the result of movie viewing, while write requests are the result of video clip editing or movie authoring procedures. Due to real-time demands of movie viewing, read requests have to be fulfilled within certain deadlines, otherwise they are considered lost. Since the data to be written into the storage device is stored in main memory buffers (or write buffers), write requests can be postponed until critical read requests are processed. However, write requests still have to be proceeded within reasonable delays and without the possibility of indefinite postponement. This is due to the physical constraint of the limited size of the main memory buffers. The new process treats both read and write requests in a homogenous manner in order to ensure that the deadlines are met and avoids indefinite postponement and large buffer sized in the case of storage device writes utilizing a single queue of requests.

Simultaneous processing of read and write requests using optimized

A method of searching for one of a plurality of objects that matches an input sequence of handwritten objects is provided. The objects are modeled by concatenating members of a set of component objects. A Trie structure representing the plurality of objects is generated. Component objects of each object are assigned to the elements of respective nodes of the Trie structure. A respective hidden Markov model (HMM) is associated with each element of each non-leaf node. The HMMs represent the respective component object of the element. A maximum probability of any HMM accepting any of the set of component objects is estimated. The root node of the Trie structure is selected. A plurality of elements of the selected node are selected. A plurality of segments of the input sequence are applied to respective HMMs associated with the selected elements to generate respective acceptance values.

Trie structure based method and apparatus for indexing and searching

A method for indexing a plurality of handwritten objects is provided. A B-tree data structure of order m is generated, where m is an integer. The B-tree has a plurality of nodes divided into a plurality of levels ordinally numbered 0.sup.th through n.sup.th. Each node in the 0.sup.th level is a leaf. Each node in the 1.sup.th level has at least m/2 leaves as children. Each one of the handwritten objects is assigned to a respective leaf. A respectively different hidden Markov model (HMM) is associated with each respective child of each of the nodes in the 1.sup.th to n.sup.th levels. Each one of the nodes in the 1.sup.th to n.sup.th levels contains the respective HMM associated with the child of the one node. Each HMM in each one of the nodes in the 1.sup.th level is trained to accept the handwritten object of the respective leaf that is a child of the one node. Each HMM associated with any of the nodes in the 2.sup.th through n.sup.th levels is trained to accept all of the handwritten objects in the leaves of a subtree that has as a root the respective child with which the HMM is associated.

Method and apparatus for indexing a plurality of handwritten objects

A method for indexing electronic handwritten documents is provided. Each document includes a plurality of output symbols in an output sequence, and is modeled by a respective Hidden Markov Model (HMM). The HMMs share a common alphabet and a common sequence length. A tree is established, having linked nodes stored in a memory. Each node has n pointers, each identifying a different node in the next level of the tree. Each path from the root to a different one of the leaf nodes defines a respective sequence of pointers. An indexing procedure is performed, for each of a subset of the nodes in one of the levels of the tree. The procedure includes: (1) determining the probability that a subset of one of the sequences of pointers leading from the root to that node represents a subset of the output symbols in one of the documents; (2) invoking the procedure for the next level, if the determined probability exceeds the minimum probability value of that level; and (3) adding a pointer to that document in the list of pointers of the leaf node associated with that sequence of pointers, if the next level is the last level and the probability is greater than the threshold value. The procedure is repeated for each other document.

Method for indexing and searching handwritten documents in a database

A method is disclosed for matching input data representing a continuous combination of input objects to a plurality of objects in a trie database structure. This data structure has a plurality of nodes partitioned into a plurality of levels. Each node in the Trie includes a plurality of elements where each element corresponds to a respective one of the component objects. In addition, a hidden Markov model corresponding to the component object is associated with the element in the database. According to the method, the input object is applied to each of the hidden Markov models associated with the respective plurality of elements of a node to generate a respective plurality of acceptance values. The element which generates the largest acceptance value is identified with a segment of the input data. The component object for this element is recorded and the identified segment is deleted from the input data string. These steps are repeated at successive levels of the Trie data structure until each segment of the input data has been identified with an element of a node of the Trie data structure. The input data is matched with the objects stored in the database by concatenating the component objects associated with the respective identified elements.

Trie based method for indexing handwritten databases

A method of searching a database having a plurality of objects is provided. Each object includes attributes and, for each attribute, a number of values. A query specifies two attributes and a maximum distance. A respective set of ranges is established for each object that has a value for the first attribute. Each set includes a range for each value of the first attribute. Each range is defined by minimum and maximum location values. A test range is established for one of the ranges. The test range has values equal to the minimum and maximum values of one of the ranges. The test range is adjusted, if necessary, so that it includes one of the values of the second attribute of the corresponding object. The test range is added to a group of ranges corresponding to the object if the minimum and maximum test values do not differ from one another by more than the maximum distance. The steps of (1) establishing a test range, (2) adjusting the test range and (3) adding the test range to the group are repeated for each range in the set of ranges corresponding to the one object. Steps (1) to (3) are repeated for each value of the second attribute of each respective object for which a set of ranges is established. Each object for which the group of ranges includes at least one range is identified as being found by the searching.

Growing community of inventors

New Brunswick, NJ, United States of America

Walid G Aref