Cụm hóa đa quan hệ là giai đoạn phân vùng đối tượng dữ liệu thành nhóm cụm dựa trên độ tương đồng của chúng, sử dụng dữ liệu trong nhiều quan hệ. CrossClus đại diện cho Cross-relational Clustering với hướng dẫn người dùng. Đây là thuật toán cụm hóa đa quan hệ phân tích cách dùng hướng dẫn người dùng trong cụm hóa và truyền播 ID tuple để tránh nối vật lý (physical joins).
Thách thức chính trong cụm hóa đa quan hệ là có nhiều thuộc tính trong nhiều quan hệ, và thường chỉ một phần nhỏ của chúng liên quan đến nhiệm vụ cụm hóa xác định.
Có thể cụm hóa sinh viên, thuộc tính bao gồm nhiều khía cạnh thông tin, bao gồm khóa học sinh viên học, ấn phẩm của sinh viên, cố vấn và nhóm nghiên cứu của sinh viên, v.v.
Người dùng thường quan tâm cụm hóa sinh viên dùng khía cạnh dữ liệu cụ thể (ví dụ: cụm hóa sinh viên theo lĩnh vực nghiên cứu). Người dùng có thể nắm tốt hơn ứng dụng cần thiết và ngữ nghĩa dữ liệu. Do đó, hướng dẫn của người dùng dưới dạng truy vấn đơn giản, có thể dùng để nâng cao hiệu quả và chất lượng cụm hóa đa quan hệ chiều cao.
CrossClus chấp nhận truy vấn người dùng bao gồm quan hệ mục tiêu (target relation) và một hoặc nhiều thuộc tính liên quan, định nghĩa mục tiêu cụm hóa của người dùng. Trong quy trình cụm hóa đa quan hệ, CrossClus cần tìm thuộc tính liên quan trên nhiều quan hệ.
CrossClus phải giải quyết hai thách thức chính trong giai đoạn tìm kiếm. Trước hết, quan hệ mục tiêu Rₜ thường có thể nối với mỗi quan hệ phi mục tiêu R qua nhiều đường dẫn nối (join paths), và mỗi thuộc tính trong R có thể dùng như thuộc tính đa quan hệ.
Không thể thực hiện bất kỳ loại tìm kiếm toàn diện nào trong không gian tìm kiếm lớn này. Thứ hai, trong số lượng lớn thuộc tính, một số liên quan đến truy vấn người dùng trong khi một số không liên quan (ví dụ: dữ liệu cá nhân bạn cùng lớp của sinh viên).
CrossClus phải thu hẹp giai đoạn tìm kiếm. Có thể xem lược đồ quan hệ như đồ thị, với quan hệ là nút và nối là cạnh. Nó áp dụng phương pháp heuristic, bắt đầu tìm kiếm từ thuộc tính do người dùng định nghĩa, và sau đó lặp lại tìm kiếm thuộc tính có lợi trong lân cận thuộc tính hiện tại. Theo cách này, nó dần mở rộng phạm vi tìm kiếm đến quan hệ kết nối, nhưng không đi xa vào hướng ngẫu nhiên.
CrossClus nhìn cách các thuộc tính cụm hóa tuple mục tiêu. Các thuộc tính liên quan được chọn dựa trên mối quan hệ của chúng với thuộc tính do người dùng định nghĩa. Nếu hai thuộc tính cụm hóa tuple rất riêng biệt, độ tương đồng của chúng thấp và chúng không có khả năng liên quan. Nếu chúng cụm hóa tuple theo cách tương tự, chúng phải được coi là liên quan.