General suffix automaton construction algorithm and space bounds

Suffix automata and factor automata are efficient data structures for representing the full index of a set of strings. They are minimal deterministic automata representing the set of all suffixes or substrings of a set of strings. This paper presents a novel analysis of the size of the suffix automaton or factor automaton of a set of strings. It shows that the suffix automaton or factor automaton of a set of strings U$U$ has at most 2Q−2$2Q-2$ states, where Q$Q$ is the number of nodes of a prefix-tree representing the strings in U$U$. This bound significantly improves over 2‖U‖−1$2\Vert U\Vert -1$, the bound given by Blumer et al. [A. Blumer, J. Blumer, D. Haussler, R.M. McConnell, A. Ehrenfeucht, Complete inverted files for efficient text retrieval and analysis, Journal of the ACM 34 (1987) 578–589], where ‖U‖$\Vert U\Vert$ is the sum of the lengths of all strings in U$U$. More generally, we give novel and general bounds for the size of the suffix or factor automaton of an automaton as a function of the size of the original automaton and the maximal length of a suffix shared by the strings it accepts. We also describe in detail a linear-time algorithm for constructing the suffix automaton S$S$ or factor automaton F$F$ of U$U$ in time O(|S|)$O\left(\left|S\right|\right)$. Our algorithm applies in fact to any input suffix-unique automaton and strictly generalizes the standard on-line construction of a suffix automaton for a single input string. Our algorithm can also be used straightforwardly to generate the suffix oracle or factor oracle of a set of strings, which has been shown to have various useful properties in string-matching. Our analysis suggests that the use of factor automata of automata can be practical for large-scale applications, a fact that is further supported by the results of our experiments applying factor automata to a music identification task with more than 15,000 songs.     

Privacy-preserving indexing of documents on the network

With the ubiquitous collection of data and creation of large distributed repositories, enabling search over this data while respecting access control is critical. A related problem is that of ensuring privacy of the content owners while still maintaining an efficient index of distributed content. We address the problem of providing privacy-preserving search over distributed access-controlled content. Indexed documents can be easily reconstructed from conventional (inverted) indexes used in search. Currently, the need to avoid breaches of access-control through the index requires the index hosting site to be fully secured and trusted by all participating content providers. This level of trust is impractical in the increasingly common case where multiple competing organizations or individuals wish to selectively share content. We propose a solution that eliminates the need of such a trusted authority. The solution builds a centralized privacy-preserving index in conjunction with a distributed access-control enforcing search protocol. Two alternative methods to build the centralized index are proposed, allowing trade offs of efficiency and security. The new index provides strong and quantifiable privacy guarantees that hold even if the entire index is made public. Experiments on a real-life dataset validate performance of the scheme. The appeal of our solution is twofold: (a) content providers maintain complete control in defining access groups and ensuring its compliance, and (b) system implementors retain tunable knobs to balance privacy and efficiency concerns for their particular domains. Dr. Vaidya’s work was supported by the National Science Foundation under grant CNS-0746943 and by a research resources grant from Rutgers Business School, Newark and New Brunswick.     

PAI: Automatic indexing for extracting asserted keywords from a document

This paper proposes an automatic indexing method named PAI (Priming Activation Indexing) that extracts keywords expressing the author’s main point from a document based on the priming effect. The basic idea is that since the author writes a document emphasizing his/her main point, impressive terms born in the mind of the reader could represent the asserted keywords. Our approach employs a spreading activation model without using corpus, thesaurus, syntactic analysis, dependency relations between terms or any other knowledge except for stop-word list. Experimental evaluations are reported by applying PAI to journal/conference papers. Naohiro Matsumura: He received his B.S. and M.S. in Engineering Science from Osaka University in 1998 and 2000. Currently, he is a Ph.D. candidate in Engineering at the University of Tokyo and a research staff of PRESTO of Japan Science and Technology Corporation (2000–). His research interests include chance discovery, computer-mediated communication, and user-oriented data mining/text mining. Yukio Ohsawa, Ph.D.: BS, U. Tokyo, 1990, MS, 1992, DS, 1995. Research associate Osaka U. (1995). Associate prof. Univ. of Tsukuba (1999–) and also researcher of Japan Science and Technology Corp (2000–). He has been working for the program com. of the Workshop on Multiagent and Cooperative Computation, Annual Conf. Japanese Soc. Artificial Intelligence, International Conf. MultiAgent Systems, Discovery Science, Pacific Asia Knowledge Discovery and Data Mining, International Conference on Web Intelligence, etc. He chaired the First International Workshop of Japanese Soc. on Artificial Intelligence, Chance Discovery International Workshop Series and the Fall Symposium on Chance Discovery from AAAI. Guest editor of Special Issues on Chance Discovery for the Journal of Contingencies and Crisis Management, Journal of Japan Society for Fuzzy Theory and intelligent informatics, regular member of editorial board for Japanese Society of Artificial Intelligence. Currently he is authoring book “Chance Discovery” from Springer Verlag, “Knowledge Managament” from Ohmsha etc. Mitsuru Ishizuka, Ph.D.: He is a professor at the Dept. of Infomation and Communication Eng., School of Information Science and Thechnology, the Univ. of Tokyo. Prior to this position, he worked at NTT Yokosuka Lab. and the Institute of Industrial Science, the Univ. of Tokyo. He earned his B.S., M.S. and Ph.D. in electronic engineering from the Univ. of Tokyo. His research interests include artificial intelligence, WWW intelligence, and multimodal lifelike agents. He is a member of IEEE, AAAI, IEICE Japan, IPS Japan, and Japanese Society for AI.     

点啮合弧面凸轮分度机构的啮合理论及分析

采用腰鼓形圆锥滚子修形结构，实现了分度凸轮与滚子间在线接触上的点啮合，使机构在原滚子瞬时接触线上的可控点处完成共轭运动。这样，既降低了机构本身对各种误差的敏感度，使之具有良好的适应性，又可保证其使用性能。     

Indexing spatiotemporal archives

Spatiotemporal objects – that is, objects that evolve over time – appear in many applications. Due to the nature of such applications, storing the evolution of objects through time in order to answer historical queries (queries that refer to past states of the evolution) requires a very large specialized database, what is termed in this article a spatiotemporal archive. Efficient processing of historical queries on spatiotemporal archives requires equally sophisticated indexing schemes. Typical spatiotemporal indexing techniques represent the objects using minimum bounding regions (MBR) extended with a temporal dimension, which are then indexed using traditional multidimensional index structures. However, rough MBR approximations introduce excessive overlap between index nodes, which deteriorates query performance. This article introduces a robust indexing scheme for answering spatiotemporal queries more efficiently. A number of algorithms and heuristics are elaborated that can be used to preprocess a spatiotemporal archive in order to produce finer object approximations, which, in combination with a multiversion index structure, will greatly improve query performance in comparison to the straightforward approaches. The proposed techniques introduce a query efficiency vs. space tradeoff that can help tune a structure according to available resources. Empirical observations for estimating the necessary amount of additional storage space required for improving query performance by a given factor are also provided. Moreover, heuristics for applying the proposed ideas in an online setting are discussed. Finally, a thorough experimental evaluation is conducted to show the merits of the proposed techniques. Edited by B. Seeger A short version of this article appeared as “Efficient indexing of spatiotemporal objects” in the Proceedings of Extending Database Technology 2002 [19]. This work was partially supported by NSF grants IIS-9907477, EIA-9983445, NSF IIS 9984729, NSF ITR 0220148, NSF IIS-0133825, NRDRP, and the U.S. Department of Defense.     

具有滚动齿的锥面包络蜗杆分度凸轮机构

提出了一种具有滚动齿的新型锥面包络蜗杆分度凸轮机构 ;推导了滚动齿廓面、凸轮廓面方程 ;引入媒介点啮合理论 ,求出共轭曲面的接触迹 ;给出滚动齿的结构设计方案。     

回转工作台槽轮分度机构设计

在分析回转工作台应用场合、工作要求、分度精度、制造成本的基础上,介绍液压驱动槽轮分度工作台的液压系统、传动机构、定位机构。详细阐述一次分度过程中,液压回路切换原理、工作装置的分度回转与复位动作过程。     

自动换刀装置中弧面分度凸轮啮合运动的力学分析

自动换刀装置中弧面分度凸轮和转动盘的滚子在啮合运动中传递较大的载荷,其大小和方向在不断发生变化,以啮合运动时转动盘的滚子为研究对象建立其受力分析的数学模型。用啮合原理及微分几何知识对数学模型中各个参数进行求解,并用VC++软件为工具对实际算例进行编程求解。得出凸轮转角与滚子所受法向载荷的变化规律曲线图,并生成载荷大小的数据文件,通过对变化规律曲线图进行分析,找出影响滚子所受法向力大小的主要因素,为设计弧面分度凸轮时转动盘滚子的选型提供理论依据。     

Context Based Adoption of Ranking and Indexing Measures for Cricket Team Ranks

There is an international cricket governing body that ranks the expertise of all the cricket playing nations, known as the International Cricket Council (ICC). The ranking system followed by the ICC relies on the winnings and defeats of the teams. The model used by the ICC to implement rankings is deficient in certain key respects. It ignores key factors like winning margin and strength of the opposition. Various measures of the ranking concept are presented in this research. The proposed methods adopt the concepts of h-Index and PageRank for presenting more comprehensive ranking metrics. The proposed approaches not only rank the teams on their losing/winning stats but also take into consideration the margin of winning and the quality of the opposition. Three cricket team ranking techniques are presented i.e., (1) Cricket Team-Index (ct-index), (2) Cricket Team Rank (CTR) and (3) Weighted Cricket Team Rank (WCTR). The proposed metrics are validated through the collection of cricket dataset, extracted from Cricinfo, having instances for all the three formats of the game i.e., T20 International (T20i), One Day International (ODI) and Test matches. The comparative analysis between the proposed and existing techniques, for all the three formats, is presented as well.