Large-scale approximate nearest neighbor search (ANNS) has become a fundamental operation in a wide range of modern applications, including recommendation systems and large language models. Partition-based indexes have emerged as a popular solution for billion-scale ANNS tasks, serving as the basis for many ANNS approaches. However, our analysis indicates that, to achieve optimal search performance on billion-scale datasets, an extremely large number of partitions (tens or even hundreds of millions) is often required for fine-grained partitioning of the feature space. Relying on full-precision distance calculations for constructing and querying such a large number of partitions imposes significant time costs. In this work, we propose a novel geometric distance inference mechanism that leverages geometric relationships to expedite distance computations between the vector and space partitions. By reusing intermediate or offline-computed distance information, this method substantially reduces the overhead of full-precision calculations. We also introduce a clustering paradigm for generating space partitions that incorporates this geometric distance pattern, which can be seamlessly integrated with other indexing schemes such as vector quantization and proximity graphs. Through detailed complexity analysis and extensive experiments on billion-scale datasets, we confirm the efficiency of our geometric index (GI) design. Empirical results show that GI-based solutions consistently surpass various baseline methods on search efficiency. In particular, they offer considerable acceleration (exceeding a factor of 2.0) at high recall levels (e.g., Recall10@10 = 95%) to partition-based solutions, while also demonstrating comparable or superior query throughput relative to leading graph-based indexes.

With the rise of machine learning models, particularly generative models like sequence-to-vector models, there is a high demand for constructing efficient approximate nearest neighbor search (ANNS) indexes on the embedding vectors they generate. Despite the development of numerous indexes for efficient vector retrieval, the complex distributions of vectors generated by these models and their impact on ANNS tasks remain underexplored. In this work, we address the challenges faced by current advanced ANNS approaches when dealing with vectors characterized by imbalanced distributions, which negatively impact search efficiency. We identify the difficulty in indexing and searching certain vectors using previous ANNS graph indexes due to skewed distributions and propose a novel index, Vista, that improves efficiency by introducing dynamic index construction patterns based on vector distribution. Our experimental evaluation confirms Vista's efficiency advantage, demonstrating that on both public and industrial-grade real-world imbalanced datasets, Vista achieves several to tens of times performance improvement compared to advanced ANNS indexes while ensuring high search accuracy and good scalability.

Approximate nearest neighbor search (ANNS) is crucial in various real-world applications, including recommendation systems, data mining, and image retrieval. To date, quantization-based algorithms have emerged as one of the most efficient solutions for ANNS on billion-scale datasets. However, the determination of the optimal number of clusters, a critical factor for peak data performance in quantization-based systems, remains inadequately explored. Previous works often propose numbers of clusters that are not optimal, and the absence of effective methodologies for tuning this parameter leads to suboptimal search performance due to the vast configuration space. In response to this challenge, this paper introduces a novel algorithm that automatically identifies the optimal number of clusters for billion-scale, quantization-based ANNS systems to maximize search efficiency. We propose an analytical model for evaluating retrieval performance, serving as the benchmark for optimizing cluster numbers in quantization-based indexes. Our algorithm applies iterative local adjustments to the ANNS index being constructed, progressively refining the number of clusters. We demonstrate the efficacy of our approach using the popular inverted index structure in quantization-based ANNS systems. Our findings indicate that: (1) By optimizing the number of clusters, the vanilla inverted index exhibits improved retrieval performance on billion-scale datasets when compared to existing state-of-the-art quantization-based methods; and (2) The additional computational overhead introduced by our optimization algorithm is minimal, even when applied to billion-scale datasets.

Cyber physical systems (CPSs) are pervasive in our daily life from mobile phones to auto driving cars.CPSs are inherently complex due to their sophisticated behaviors and thus difficult to build.In this paper, we propose a systematic approach to develop CPSs with quality assurance throughout the development process.A CPS is abstracted and partitioned into a set of independent executing agents, where each agent is further refined into a set of behaviors.Each behavior is modeled with a high level Petri net, called behavior net.The overall behavior of an agent is modeled by an agent through composing individual behavior nets.Finally, the overall system behavior is modeled by a system net through integrating individual agent nets incrementally.Simulation and model checking can be performed on individual behavior nets, agent nets, and the final system net.The resulting system net is systematically mapped to behavior programs in Java, which are enhanced and extended with domain specific functionality.A set of property patterns based on behavior program is developed, which are used to generate runtime monitors to check behavior program executions.We demonstrate our approach using a multi-car parking system.

Cyber physical systems (CPSs) are pervasive in our daily life from mobile phones to auto driving cars.CPSs are inherently complex due to their sophisticated behaviors and thus difficult to build.In this paper, we propose a framework to develop CPSs based on a model driven approach with quality assurance throughout the development process.An agent-oriented approach is used to model individual physical and computation processes using high level Petri nets, and an aspect-oriented approach is used to integrate individual models.The Petri net models are systematically mapped to classes and threads in Java, which are enhanced and extended with domain specific functionalities.Complementary quality assurance techniques are applied throughout system development and deployment, including simulation and model checking of design models, model checking of Java code, and run-time verification of Java executable.We demonstrate our framework using a car parking system.

Cyber-physical systems (CPSs) are pervasive in our daily life from mobile phones to auto-driving cars. CPSs are inherently complex due to their sophisticated behaviors and thus difficult to build. In this paper, we propose a framework to develop CPSs based on a model-driven approach with quality assurance throughout the development process. An agent-oriented approach is used to model individual physical and computation processes using high-level Petri nets, and an aspect-oriented approach is used to integrate individual models. The Petri net models are systematically mapped to classes and threads in Java, which are enhanced and extended with domain-specific functionalities. Complementary quality assurance techniques are applied throughout system development and deployment, including simulation and model checking of design models, model checking of Java code, and runtime verification of Java executable. We demonstrate our framework using a car parking system.

Self-adaptive intelligent vehicle system has become more attractive due to its capability of adaptation to varying and stochastic environments in an efficient and autonomous manner. The dynamic demeanor in adaptation and reconfiguration of intelligent vehicle systems will facilitate the existing federal and civil construction in better planning as well as in abbreviating the huge amount of budget of government and will ameliorate and impoverish the day to day lifestyle of mass generation with enhanced efficiency in green-energy oriented transportation systems. However, such systems may be prone to runtime failures when the overall environmental dynamics as well as the required parameters cannot be adequately considered during design time. In this project, we have examined and investigated the typical safety critical issues using SMT solver on a speed synchronization racing car example in both design and implementation level. In the design level, a Petri Net model is adopted as the high level abstraction of the racing car. In the implementation level, the system was developed in Java and Lejos package since the application toolkit is LEGO mindstorm EV3 robotic kit. In addition to this, both a set of safety properties and Petri Net model was rewritten in Z3 specification, where the safety properties are verified against the system model. The observed results of the specified properties have demonstrated that all required system constraints for hardware and firmware were analyzed and verified on an optimized version of Petri Net model of the system. This is the first time, from our literature review, to see the validation of the both design and implementation level using SMT Solver. Furthermore, this result has provided strong and rigid foundation for the runtime verification of cyber physical systems.

Security has become an essential and critical nonfunctional requirement of modern software systems, especially cyber physical systems.Security patterns aim at capturing security expertise in the worked solutions to recurring security design problems.This paper presents an approach to formally model and analyze six security patterns to detect potential incompleteness, inconsistency, and ambiguity in the textual descriptions; and to prevent their incorrect implementation.These patterns are modeled using high level Petri nets in our tool environment PIPE+.Simulation is used to analyze various security relevant properties.The validated formal models of individual security patterns serve as the building blocks for system design involving the composition of multiple security patterns.

No abstract available.

Innovative learning methodologies and tools are needed to foster students' interest in programming, improve the effectiveness of programming teaching, and retain the students in computing programs. We present a Collaborative Interactive Cyber learning Platform for Anywhere Anytime Java Programming Learning, an open-source cyber learning platform for Computer Science programming education, to support anywhere anytime personalized and collaborative programming learning. A preliminary evaluation of the proposed cyber learning platform and learning methods has been conducted and the students' responses have been very positive.

A software architecture design has many benefits including aiding comprehension, supporting early analysis, and providing guidance for subsequent development activities. An additional major benefit is if a partial prototype implementation can be automatically generated from a given software architecture design. However, in the past decade less progress was made on automatically realizing software architecture designs. In this paper, we present a translator for automatically generating an implementation from a software architectural description. The implementation not only captures the functionality of the given architecture description, but also contains additional monitoring code for ensuring desirable behavior properties through runtime verification. Our method takes a software description written in SAM, a software architecture model integrating dual formal methods Petri nets and temporal logic, and generates ArchJava/Java/AspectJ code. More specifically, the structure of a SAM architecture description produces ArchJava code, the behavior models of components/connectors represented in Petri nets lead to plain Java code, and the property specifications defined in temporal logic generate AspectJ code; the above code segments are then integrated into Java code. An experimental result is provided.

Current service architecture description language and composition approaches consider simplistic method invocation. They pay less attention to the formal semantics and verification of service composition in the design, and less support property specifications and architecture validation. This paper presents an executable web service architecture model, Service-Oriented Software Architecture Model (SO-SAM), which is an extension of SAM (Software Architecture Model [16]) to the web service applications, and verificationof web system properties in the design. SO-SAM describes each web service in terms of component and service composition in terms of connector separately. Furthermore, we validate SO-SAM model to prove that it facilitates the verification and monitoring of web services integration through translation to the Maude programming langauge, a high level language and high performance executable specification with the componentized and object-oriented design, as well as using model checking technique in the system design level. Finally, a case study of the validation of the model is demonstrated.

Software architectures shift developers' focus from lines-of-code to coarser-grained architectural elements and their interconnection structure. However, the benefits of architecture description languages (ADLs) cannot be fully captured without an automated realization of software architecture designs because manually shifting from a model to its implementation is error-prone. We propose an integrated approach for automatically translating software architecture design models to an implementation and validating the translation as well as the implementation by exploring runtime verification technique and aspect-oriented programming. Specifically, system properties are not only verified against design models, but also verified during the execution of the generated implementation of software architecture design. A prototype tool, SAM Parser, is developed to demonstrate the approach on SAM (Software Architecture Model). In SAM Parser, all the realization and verification code can be automatically generated without human intervention. In this paper, we first brief describe the approach report on a case study conducted at an e-commerce scenario, an online shopping system to assess the benefits of automated realization of software architecture design and validation in a Web service domain.