Computer (digital) forensic examiners typically write a report to document the examination process, including tools used, major processing steps, summary of the findings, and a detailed listing of relevant evidence (files, artifacts) exported to external media (CD, DVD, hard copy) for the case investigator or attorney. However, proper interpretation of the significance of extracted evidence often requires additional consultation with the examiner. This paper proposes a practical methodology for transforming the findings in typical forensic reports to a graphical representation using Bayesian networks (BNs). BNs offer the following advantages: (1) Delineate the cause-effect relationship among relevant pieces of evidence described in the report; and (2) Use probability and established Bayesian inference rules to deal with uncertainty of digital evidence. A realistic forensic report is used to demonstrate this methodology.

We examine the problem of efficient distance-based similarity search over high-dimensional data. We show that a promising approach to this problem is to reduce dimensions and allow fast approximation. Conventional reduction approaches, however, entail a significant shortcoming: The approximation volume extends across the dataspace, which causes overestimation of retrieval sets and impairs performance. This paper focuses on a new criterion for dimensionality reduction methods: bounded approximation. We show that this requirement can be accomplished by a novel nonlinear transformation scheme that extracts two important parameters from the data. We devise two approximation formulations, namely, rectangular and spherical range search, each corresponding to a closed volume around the original search sphere. We discuss in detail how we can derive tight bounds for the parameters and prove further results, as well as highlight insights into the problems and our proposed solutions. To demonstrate the benefits of the new criterion, we study the effects of (un)boundedness on approximation performance, including selectivity, error toleration, and efficiency. Extensive experiments confirm the superiority of this technique over recent state-of-the-art schemes.

To enable efficient similarity search in large databases, many indexing techniques use a linear transformation scheme to reduce dimensions and allow fast approximation. In this reduction approach the approximation is unbounded, so that the approximation volume extends across the dataspace. This causes over-estimation of retrieval sets and impairs performance.This paper presents a non-linear transformation scheme that extracts two important parameters specifying the data. We prove that these parameters correspond to a bounded volume around the search sphere, irrespective of dimensionality. We use a special workspace-mapping mechanism to derive tight bounds for the parameters and to prove further results, as well as highlighting insights into the problems and our proposed solutions. We formulate a measure that lower-bounds the Euclidean distance, and discuss the implementation of the technique upon a popular index structure. Extensive experiments confirm the superiority of this technique over recent state-of-the-art schemes.

We propose a novel, shape-matching algorithm using skeletal graphs. The topology of skeletal graphs is captured and compared at the node level. Such graph representation allows preservation of the skeletal graph's coherence without scarifying the flexibility of matching similar portions of graphs across different levels. By using an appropriate sampling resolution, we are able to achieve a high recognition rate, and at the same time, significantly reduce the space and time complexity of matching. We tested our approach against the directed acyclic graph (DAG) method on noisy graphs and occluded or cluttered scenes. The results show that our approach is an effective and efficient technique for shape recognition.

We propose several algorithms using the vector space model to classify the news articles posted on the NETNEWS according to the newsgroup categories. The baseline method combines the terms of all the articles of each newsgroup in the training set to represent the newsgroups as single vectors. After training, the incoming news articles are classified based on their similarity to the existing newsgroup categories. We propose to use the following techniques to improve the classification performance of the baseline method: (1) use routing (classification) accuracy and the similarity values to refine the training set; (2) update the underlying term structures periodically during testing; and (3) apply k-means clustering to partition the newsgroup articles and represent each newsgroup by k vectors. Our test collection consists of the real news articles and the 519 subnewsgroups under the REC newsgroup of NETNEWS in a period of 3 months. Our experimental results demonstrate that the technique of refining the training set reduces from one-third to two-thirds of the storage. The technique of periodical updates improves the routing accuracy ranging from 20% to 100% but incurs runtime overhead. Finally, representing each newsgroup by k vectors (with k = 2 or 3) using clustering yields the most significant improvement in routing accuracy, ranging from 60% to 100%, while causing only slightly higher storage requirements.

We propose a statistical feature reduction technique to filter out the most ambiguous articles in the training data for categorizing NETNEWS articles. We also incorporate a batch updating scheme to periodically do maintenance on the term structures of the news database after training. The baseline method combines the terms of all the articles of each newsgroup in the training set to represent the newsgroups as single vectors. After training, the incoming news articles are classified based on their similarity to the existing newsgroup categories. Our implementation uses an inverted file to store the trained term structures of each newsgroup, and uses a list similar to the inverted file to buffer the newly arrived articles, for efficient routing and updating purposes. Our experimental results using real NETNEWS articles and newsgroups demonstrate that: (1) applying feature reduction to the training set improves the routing accuracy, efficiency and database storage, (2) updating improves the routing accuracy; and (3) the batch technique improves the efficiency of the updating operation.

We describe a natural extension of the banker's algorithm (D.W. Dijkstra, 1968) for deadlock avoidance in operating systems. Representing the control flow of each process as a rooted tree of nodes corresponding to resource requests and releases, we propose a quadratic-time algorithm which decomposes each flow graph into a nested family of regions, such that all allocated resources are released before the control leaves a region. Also, information on the maximum resource claims for each of the regions can be extracted prior to process execution. By inserting operating system calls when entering a new region for each process at runtime, and applying the original banker's algorithm for deadlock avoidance, this method has the potential to achieve better resource utilization because information on the "localized approximate maximum claims" is used for testing system safety.

We extend a torus-based coterie structure for distributed mutual exclusion to allow k multiple entries in a critical section. In the original coterie, the system nodes are logically arranged in a rectangle, called a torus, in which the last row (column) is followed by the first row (column) using end wraparound. A torus quorum consists of a head and a tail, where the head contains one entire row and the tail contains one node from each of the s succeeding rows, s/spl ges/1 is a system parameter. It has been shown that by setting s=[h/2], where h=the number of rows, the collection of torus quorums form an equal-sized, equal-responsibility coterie. In this paper we propose two extensions to k-coteries: the Div-Torus method divides the system nodes into k clusters and runs a separate instance of a torus coterie in each cluster; the k-Torus method uses quorums of tail s=[h/(k+1)]. We compare the quorum size and quorum availability of the two proposed methods, and against the DIV method which is based on the majority quorums in each of the k divided clusters, assuming the node reliability is a constant. Numerical data demonstrate that DIV and Div-Torus have similar system availability, better than that of the k-Torus, although all 3 methods' availability becomes comparable when the node reliability is higher than 0.9. However, Div-Torus has the smallest quorum size and k-Torus the second smallest, which has the potential of causing less network traffic when requesting permissions from a quorum.

We incorporate the Latent Semantic Indexing (LSl) technique into a competition-based neural network model for information retrieval.The original neural network model was based on a causal inference network, incorporating Roget's Thesaurus, that connects the index terms and related documents.Since the pmcIess of creating or updating a thesaurus is rather expensive, we apply the LSI technique to provide an automated procedure that captures the semantic relationship between the doctrments and index terms.C)ur experimental results using four standard text collections show that the LSI-baaed model generates appreciable improvement in retrieval effectiveness with faster query evaluation over the thesatrrus-ba~sed model.

We adapt a competition-based connectionist model to information retrieval. This model, which has been proposed for diagnostic problem solving, treats documents as "disorders" and user information needs as "manifestations", and it uses a competitive activation mechanism which converges to a set of disorders that best explain the given manifestations. Our experimental results using four standard document collections demonstrate the efficiency and the retrieval precision of this model, comparable to or better than that of various information retrieval models reported in the literature. We also propose a parallel implementation of the model on a SIMD machine, MasPar's MP-I. Our experimental results demonstrate the potential to achieve significant speedups.>

This paper investigates a network-based information retrieval model using diagnostic inferencing techniques. A basic inference network in information retrieval consists of two component networks: the document component and the query component. In our approach, there is a layer of nodes corresponding to the documents, and a layer of nodes corresponding to the index terms extracted from the document set, with links connecting documents to the related index terms 1. A thesaurus is used to provide concept categories; these categories are represented by another layer of nodes, with links connecting the index terms and the related categories 2. The query component uses a symmetric structure. Each query causes markings of category nodes, hence markings of the related index term nodes, in the document component of the network. In our previous work, we adapted a competition-based connectionist model for diagnostic problem solving to information retrieval. In this model, documents are treated as “disorders” and user information needs, represented by the marked index term nodes, as “manifestations”. A competitive activation mechanism is then used which converges to a set of disorders that best explain the given manifestations. Our experiments showed that the retrieval performance of this model is comparable to or better than that of various information retrieval models reported in the literature. In this paper, we report further enhancements of the model by using a merged thesaurus.

We present a token-based algorithm for solving the K-entry critical section problem. Based on Raymond's (1989) tree-based approach, we regard the nodes as being arranged in a directed tree structure, and all messages used in the algorithm are sent along the directed edges of the tree. There are K tokens in the system; we use a bag structure at each node to record the collection of the neighboring nodes, possibly with multiple occurrences of the same node, through which the K tokens can be located. As a result, there are K paths from each node leading to the K tokens in the system. Our algorithm requires at most 2 KD messages for a node to enter the CS, where D is the diameter of the tree. Therefore, when the diameter D is much smaller than N, the number of nodes, e.g. D=O(1) as in a star or D=O(logN) as in a binary tree, our algorithm's upper bound on the number of messages per CS is smaller than those previously reported.

It has been demonstrated that simulated annealing provides high-quality results for the data clustering problem. However, existing simulated annealing schemes are memory-based algorithms; they are not suited for solving large problems such as data clustering which typically are too big to fit in the memory space in its entirety. Various buffer replacement policies, assuming either temporal or spatial locality, are not useful in this case since simulated annealing is based on a randomized search process. Poor locality of references will cause the memory to thrash because too many replacements are required. This phenomenon will incur excessive disk accesses and force the machine to run at the speed of the I/O subsystem. In this paper, we formulate the data clustering problem as a graph partition problem (GPP), and propose a decomposition-based approach to address the issue of excessive disk accesses during annealing. We apply the statistical sampling technique to randomly select subgraphs of the GPP into memory for annealing. Both the analytical and experimental studies indicate that the decomposition-based approach can dramatically reduce the costly disk I/O activities while obtaining excellent optimized results.

Closed-form, nonrecurrent expressions for the cost of completely and partly unsuccessful batched searching are developed for complete j-ary tree files. These expressions are applied to both the replacement and nonreplacement models of the search queries. The expressions provide more efficient formulas than previously reported for calculating the cost of batched searching. The expressions can also be used to estimate the number of block accesses for hierarchical file structures.>

A direct and unified approach is used to analyze the efficiency of batched searching of sequential and tree-structured files. The analysis is applicable to arbitrary search distributions, and closed-form expressions are obtained for the expected batched searching cost and savings. In particular, we consider a search distribution satisfying Zipf's law for sequential files and four types of uniform (random) search distribution for sequential and tree-structured files. These results unify and extend earlier research on batched searching and estimating block accesses for database systems.

This paper presents a combined algorithm to perform batch insertion, deletion, and update for tree structured files. The efficiency of the algorithm is analyzed for performing updates only and insertions only. A cost analysis example is reviewed to demonstrate that batch operations for tree structured files achieve the advantages of a differential database representation and, at the same time, avoid the drawbacks previously attributed to the use of differential files.